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