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