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