PrologEpilogInserter.cpp revision 920595a960fbebbf614dd159d54fc2e7ea279c22
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 TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 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 (!TII.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 TII.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 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 (!TII.restoreCalleeSavedRegisters(*MBB, I, CSI)) { 283 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 284 TII.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