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