PrologEpilogInserter.cpp revision 4188699f80c233a20b6ddc61570a8a8c1804cb85
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/Target/TargetMachine.h" 24#include "llvm/Target/MRegisterInfo.h" 25#include "llvm/Target/TargetFrameInfo.h" 26#include "llvm/Target/TargetInstrInfo.h" 27using namespace llvm; 28 29namespace { 30 struct PEI : public MachineFunctionPass { 31 const char *getPassName() const { 32 return "Prolog/Epilog Insertion & Frame Finalization"; 33 } 34 35 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract 36 /// frame indexes with appropriate references. 37 /// 38 bool runOnMachineFunction(MachineFunction &Fn) { 39 // Get MachineDebugInfo so that we can track the construction of the 40 // frame. 41 if (MachineDebugInfo *DI = getAnalysisToUpdate<MachineDebugInfo>()) { 42 Fn.getFrameInfo()->setMachineDebugInfo(DI); 43 } 44 45 // Scan the function for modified caller saved registers and insert spill 46 // code for any caller saved registers that are modified. Also calculate 47 // the MaxCallFrameSize and HasCalls variables for the function's frame 48 // information and eliminates call frame pseudo instructions. 49 calculateCallerSavedRegisters(Fn); 50 51 // Add the code to save and restore the caller saved registers 52 saveCallerSavedRegisters(Fn); 53 54 // Allow the target machine to make final modifications to the function 55 // before the frame layout is finalized. 56 Fn.getTarget().getRegisterInfo()->processFunctionBeforeFrameFinalized(Fn); 57 58 // Calculate actual frame offsets for all of the abstract stack objects... 59 calculateFrameObjectOffsets(Fn); 60 61 // Add prolog and epilog code to the function. This function is required 62 // to align the stack frame as necessary for any stack variables or 63 // called functions. Because of this, calculateCallerSavedRegisters 64 // must be called before this function in order to set the HasCalls 65 // and MaxCallFrameSize variables. 66 insertPrologEpilogCode(Fn); 67 68 // Replace all MO_FrameIndex operands with physical register references 69 // and actual offsets. 70 // 71 replaceFrameIndices(Fn); 72 73 RegsToSave.clear(); 74 StackSlots.clear(); 75 return true; 76 } 77 78 private: 79 std::vector<std::pair<unsigned, const TargetRegisterClass*> > RegsToSave; 80 std::vector<int> StackSlots; 81 82 void calculateCallerSavedRegisters(MachineFunction &Fn); 83 void saveCallerSavedRegisters(MachineFunction &Fn); 84 void calculateFrameObjectOffsets(MachineFunction &Fn); 85 void replaceFrameIndices(MachineFunction &Fn); 86 void insertPrologEpilogCode(MachineFunction &Fn); 87 }; 88} 89 90 91/// createPrologEpilogCodeInserter - This function returns a pass that inserts 92/// prolog and epilog code, and eliminates abstract frame references. 93/// 94FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); } 95 96 97/// calculateCallerSavedRegisters - Scan the function for modified caller saved 98/// registers. Also calculate the MaxCallFrameSize and HasCalls variables for 99/// the function's frame information and eliminates call frame pseudo 100/// instructions. 101/// 102void PEI::calculateCallerSavedRegisters(MachineFunction &Fn) { 103 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 104 const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo(); 105 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 106 107 // Get the callee saved register list... 108 const unsigned *CSRegs = RegInfo->getCalleeSaveRegs(); 109 110 // Get the function call frame set-up and tear-down instruction opcode 111 int FrameSetupOpcode = RegInfo->getCallFrameSetupOpcode(); 112 int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode(); 113 114 // Early exit for targets which have no callee saved registers and no call 115 // frame setup/destroy pseudo instructions. 116 if ((CSRegs == 0 || CSRegs[0] == 0) && 117 FrameSetupOpcode == -1 && FrameDestroyOpcode == -1) 118 return; 119 120 unsigned MaxCallFrameSize = 0; 121 bool HasCalls = false; 122 123 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) 124 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) 125 if (I->getOpcode() == FrameSetupOpcode || 126 I->getOpcode() == FrameDestroyOpcode) { 127 assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo" 128 " instructions should have a single immediate argument!"); 129 unsigned Size = I->getOperand(0).getImmedValue(); 130 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size; 131 HasCalls = true; 132 RegInfo->eliminateCallFramePseudoInstr(Fn, *BB, I++); 133 } else { 134 ++I; 135 } 136 137 MachineFrameInfo *FFI = Fn.getFrameInfo(); 138 FFI->setHasCalls(HasCalls); 139 FFI->setMaxCallFrameSize(MaxCallFrameSize); 140 141 // Now figure out which *callee saved* registers are modified by the current 142 // function, thus needing to be saved and restored in the prolog/epilog. 143 // 144 const bool *PhysRegsUsed = Fn.getUsedPhysregs(); 145 const TargetRegisterClass* const *CSRegClasses = 146 RegInfo->getCalleeSaveRegClasses(); 147 for (unsigned i = 0; CSRegs[i]; ++i) { 148 unsigned Reg = CSRegs[i]; 149 if (PhysRegsUsed[Reg]) { 150 // If the reg is modified, save it! 151 RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i])); 152 } else { 153 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 154 *AliasSet; ++AliasSet) { // Check alias registers too. 155 if (PhysRegsUsed[*AliasSet]) { 156 RegsToSave.push_back(std::make_pair(Reg, CSRegClasses[i])); 157 break; 158 } 159 } 160 } 161 } 162 163 if (RegsToSave.empty()) 164 return; // Early exit if no caller saved registers are modified! 165 166 unsigned NumFixedSpillSlots; 167 const std::pair<unsigned,int> *FixedSpillSlots = 168 TFI->getCalleeSaveSpillSlots(NumFixedSpillSlots); 169 170 // Now that we know which registers need to be saved and restored, allocate 171 // stack slots for them. 172 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 173 unsigned Reg = RegsToSave[i].first; 174 const TargetRegisterClass *RC = RegsToSave[i].second; 175 176 // Check to see if this physreg must be spilled to a particular stack slot 177 // on this target. 178 const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots; 179 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots && 180 FixedSlot->first != Reg) 181 ++FixedSlot; 182 183 int FrameIdx; 184 if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) { 185 // Nope, just spill it anywhere convenient. 186 FrameIdx = FFI->CreateStackObject(RC->getSize(), RC->getAlignment()); 187 } else { 188 // Spill it to the stack where we must. 189 FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second); 190 } 191 StackSlots.push_back(FrameIdx); 192 } 193} 194 195/// saveCallerSavedRegisters - Insert spill code for any caller saved registers 196/// that are modified in the function. 197/// 198void PEI::saveCallerSavedRegisters(MachineFunction &Fn) { 199 // Early exit if no caller saved registers are modified! 200 if (RegsToSave.empty()) 201 return; 202 203 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 204 205 // Now that we have a stack slot for each register to be saved, insert spill 206 // code into the entry block. 207 MachineBasicBlock *MBB = Fn.begin(); 208 MachineBasicBlock::iterator I = MBB->begin(); 209 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 210 // Insert the spill to the stack frame. 211 RegInfo->storeRegToStackSlot(*MBB, I, RegsToSave[i].first, StackSlots[i], 212 RegsToSave[i].second); 213 } 214 215 // Add code to restore the callee-save registers in each exiting block. 216 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 217 for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI) 218 // If last instruction is a return instruction, add an epilogue. 219 if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) { 220 MBB = FI; 221 I = MBB->end(); --I; 222 223 // Skip over all terminator instructions, which are part of the return 224 // sequence. 225 MachineBasicBlock::iterator I2 = I; 226 while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode())) 227 I = I2; 228 229 bool AtStart = I == MBB->begin(); 230 MachineBasicBlock::iterator BeforeI = I; 231 if (!AtStart) 232 --BeforeI; 233 234 // Restore all registers immediately before the return and any terminators 235 // that preceed it. 236 for (unsigned i = 0, e = RegsToSave.size(); i != e; ++i) { 237 RegInfo->loadRegFromStackSlot(*MBB, I, RegsToSave[i].first, 238 StackSlots[i], RegsToSave[i].second); 239 assert(I != MBB->begin() && 240 "loadRegFromStackSlot didn't insert any code!"); 241 // Insert in reverse order. loadRegFromStackSlot can insert multiple 242 // instructions. 243 if (AtStart) 244 I = MBB->begin(); 245 else { 246 I = BeforeI; 247 ++I; 248 } 249 } 250 } 251} 252 253 254/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 255/// abstract stack objects. 256/// 257void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 258 const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo(); 259 260 bool StackGrowsDown = 261 TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown; 262 263 // Loop over all of the stack objects, assigning sequential addresses... 264 MachineFrameInfo *FFI = Fn.getFrameInfo(); 265 266 unsigned StackAlignment = TFI.getStackAlignment(); 267 unsigned MaxAlign = 0; 268 269 // Start at the beginning of the local area. 270 // The Offset is the distance from the stack top in the direction 271 // of stack growth -- so it's always positive. 272 int Offset = TFI.getOffsetOfLocalArea(); 273 if (StackGrowsDown) 274 Offset = -Offset; 275 assert(Offset >= 0 276 && "Local area offset should be in direction of stack growth"); 277 278 // If there are fixed sized objects that are preallocated in the local area, 279 // non-fixed objects can't be allocated right at the start of local area. 280 // We currently don't support filling in holes in between fixed sized objects, 281 // so we adjust 'Offset' to point to the end of last fixed sized 282 // preallocated object. 283 for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) { 284 int FixedOff; 285 if (StackGrowsDown) { 286 // The maximum distance from the stack pointer is at lower address of 287 // the object -- which is given by offset. For down growing stack 288 // the offset is negative, so we negate the offset to get the distance. 289 FixedOff = -FFI->getObjectOffset(i); 290 } else { 291 // The maximum distance from the start pointer is at the upper 292 // address of the object. 293 FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i); 294 } 295 if (FixedOff > Offset) Offset = FixedOff; 296 } 297 298 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) { 299 // If stack grows down, we need to add size of find the lowest 300 // address of the object. 301 if (StackGrowsDown) 302 Offset += FFI->getObjectSize(i); 303 304 unsigned Align = FFI->getObjectAlignment(i); 305 // If the alignment of this object is greater than that of the stack, then 306 // increase the stack alignment to match. 307 MaxAlign = std::max(MaxAlign, Align); 308 // Adjust to alignment boundary 309 Offset = (Offset+Align-1)/Align*Align; 310 311 if (StackGrowsDown) { 312 FFI->setObjectOffset(i, -Offset); // Set the computed offset 313 } else { 314 FFI->setObjectOffset(i, Offset); 315 Offset += FFI->getObjectSize(i); 316 } 317 } 318 319 // Align the final stack pointer offset, but only if there are calls in the 320 // function. This ensures that any calls to subroutines have their stack 321 // frames suitable aligned. 322 if (FFI->hasCalls()) 323 Offset = (Offset+StackAlignment-1)/StackAlignment*StackAlignment; 324 325 // Set the final value of the stack pointer... 326 FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea()); 327 328 // Remember the required stack alignment in case targets need it to perform 329 // dynamic stack alignment. 330 assert(FFI->getMaxAlignment() == MaxAlign && 331 "Stack alignment calculation broken!"); 332} 333 334 335/// insertPrologEpilogCode - Scan the function for modified caller saved 336/// registers, insert spill code for these caller saved registers, then add 337/// prolog and epilog code to the function. 338/// 339void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 340 // Add prologue to the function... 341 Fn.getTarget().getRegisterInfo()->emitPrologue(Fn); 342 343 // Add epilogue to restore the callee-save registers in each exiting block 344 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 345 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 346 // If last instruction is a return instruction, add an epilogue 347 if (!I->empty() && TII.isReturn(I->back().getOpcode())) 348 Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I); 349 } 350} 351 352 353/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 354/// register references and actual offsets. 355/// 356void PEI::replaceFrameIndices(MachineFunction &Fn) { 357 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 358 359 const TargetMachine &TM = Fn.getTarget(); 360 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 361 const MRegisterInfo &MRI = *TM.getRegisterInfo(); 362 363 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) 364 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) 365 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 366 if (I->getOperand(i).isFrameIndex()) { 367 // If this instruction has a FrameIndex operand, we need to use that 368 // target machine register info object to eliminate it. 369 MRI.eliminateFrameIndex(I); 370 break; 371 } 372} 373