PrologEpilogInserter.cpp revision 00dff8dda29b5a249cd99405ce26e84cef13ba53
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 252 // Do not insert prologue code before debug LABELs at the start of the 253 // entry block. 254 MachineModuleInfo *MMI = FFI->getMachineModuleInfo(); 255 if (MMI && MMI->hasDebugInfo()) 256 while (I != MBB->end() && I->getOpcode() == TargetInstrInfo::LABEL) 257 ++I; 258 259 if (!TII.spillCalleeSavedRegisters(*MBB, I, CSI)) { 260 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 261 // Add the callee-saved register as live-in. It's killed at the spill. 262 MBB->addLiveIn(CSI[i].getReg()); 263 264 // Insert the spill to the stack frame. 265 TII.storeRegToStackSlot(*MBB, I, CSI[i].getReg(), true, 266 CSI[i].getFrameIdx(), CSI[i].getRegClass()); 267 } 268 } 269 270 // Add code to restore the callee-save registers in each exiting block. 271 for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI) 272 // If last instruction is a return instruction, add an epilogue. 273 if (!FI->empty() && FI->back().getDesc().isReturn()) { 274 MBB = FI; 275 I = MBB->end(); --I; 276 277 // Skip over all terminator instructions, which are part of the return 278 // sequence. 279 MachineBasicBlock::iterator I2 = I; 280 while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator()) 281 I = I2; 282 283 bool AtStart = I == MBB->begin(); 284 MachineBasicBlock::iterator BeforeI = I; 285 if (!AtStart) 286 --BeforeI; 287 288 // Restore all registers immediately before the return and any terminators 289 // that preceed it. 290 if (!TII.restoreCalleeSavedRegisters(*MBB, I, CSI)) { 291 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 292 TII.loadRegFromStackSlot(*MBB, I, CSI[i].getReg(), 293 CSI[i].getFrameIdx(), 294 CSI[i].getRegClass()); 295 assert(I != MBB->begin() && 296 "loadRegFromStackSlot didn't insert any code!"); 297 // Insert in reverse order. loadRegFromStackSlot can insert multiple 298 // instructions. 299 if (AtStart) 300 I = MBB->begin(); 301 else { 302 I = BeforeI; 303 ++I; 304 } 305 } 306 } 307 } 308} 309 310 311/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 312/// abstract stack objects. 313/// 314void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 315 const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo(); 316 317 bool StackGrowsDown = 318 TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown; 319 320 // Loop over all of the stack objects, assigning sequential addresses... 321 MachineFrameInfo *FFI = Fn.getFrameInfo(); 322 323 unsigned MaxAlign = 0; 324 325 // Start at the beginning of the local area. 326 // The Offset is the distance from the stack top in the direction 327 // of stack growth -- so it's always positive. 328 int64_t Offset = TFI.getOffsetOfLocalArea(); 329 if (StackGrowsDown) 330 Offset = -Offset; 331 assert(Offset >= 0 332 && "Local area offset should be in direction of stack growth"); 333 334 // If there are fixed sized objects that are preallocated in the local area, 335 // non-fixed objects can't be allocated right at the start of local area. 336 // We currently don't support filling in holes in between fixed sized objects, 337 // so we adjust 'Offset' to point to the end of last fixed sized 338 // preallocated object. 339 for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) { 340 int64_t FixedOff; 341 if (StackGrowsDown) { 342 // The maximum distance from the stack pointer is at lower address of 343 // the object -- which is given by offset. For down growing stack 344 // the offset is negative, so we negate the offset to get the distance. 345 FixedOff = -FFI->getObjectOffset(i); 346 } else { 347 // The maximum distance from the start pointer is at the upper 348 // address of the object. 349 FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i); 350 } 351 if (FixedOff > Offset) Offset = FixedOff; 352 } 353 354 // First assign frame offsets to stack objects that are used to spill 355 // callee saved registers. 356 if (StackGrowsDown) { 357 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) { 358 // If stack grows down, we need to add size of find the lowest 359 // address of the object. 360 Offset += FFI->getObjectSize(i); 361 362 unsigned Align = FFI->getObjectAlignment(i); 363 // If the alignment of this object is greater than that of the stack, then 364 // increase the stack alignment to match. 365 MaxAlign = std::max(MaxAlign, Align); 366 // Adjust to alignment boundary 367 Offset = (Offset+Align-1)/Align*Align; 368 369 FFI->setObjectOffset(i, -Offset); // Set the computed offset 370 } 371 } else { 372 for (unsigned i = MaxCSFrameIndex; i >= MinCSFrameIndex; --i) { 373 unsigned Align = FFI->getObjectAlignment(i); 374 // If the alignment of this object is greater than that of the stack, then 375 // increase the stack alignment to match. 376 MaxAlign = std::max(MaxAlign, Align); 377 // Adjust to alignment boundary 378 Offset = (Offset+Align-1)/Align*Align; 379 380 FFI->setObjectOffset(i, Offset); 381 Offset += FFI->getObjectSize(i); 382 } 383 } 384 385 // Make sure the special register scavenging spill slot is closest to the 386 // frame pointer if a frame pointer is required. 387 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 388 if (RS && RegInfo->hasFP(Fn)) { 389 int SFI = RS->getScavengingFrameIndex(); 390 if (SFI >= 0) { 391 // If stack grows down, we need to add size of the lowest 392 // address of the object. 393 if (StackGrowsDown) 394 Offset += FFI->getObjectSize(SFI); 395 396 unsigned Align = FFI->getObjectAlignment(SFI); 397 // Adjust to alignment boundary 398 Offset = (Offset+Align-1)/Align*Align; 399 400 if (StackGrowsDown) { 401 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset 402 } else { 403 FFI->setObjectOffset(SFI, Offset); 404 Offset += FFI->getObjectSize(SFI); 405 } 406 } 407 } 408 409 // Then assign frame offsets to stack objects that are not used to spill 410 // callee saved registers. 411 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) { 412 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 413 continue; 414 if (RS && (int)i == RS->getScavengingFrameIndex()) 415 continue; 416 417 // If stack grows down, we need to add size of find the lowest 418 // address of the object. 419 if (StackGrowsDown) 420 Offset += FFI->getObjectSize(i); 421 422 unsigned Align = FFI->getObjectAlignment(i); 423 // If the alignment of this object is greater than that of the stack, then 424 // increase the stack alignment to match. 425 MaxAlign = std::max(MaxAlign, Align); 426 // Adjust to alignment boundary 427 Offset = (Offset+Align-1)/Align*Align; 428 429 if (StackGrowsDown) { 430 FFI->setObjectOffset(i, -Offset); // Set the computed offset 431 } else { 432 FFI->setObjectOffset(i, Offset); 433 Offset += FFI->getObjectSize(i); 434 } 435 } 436 437 // Make sure the special register scavenging spill slot is closest to the 438 // stack pointer. 439 if (RS && !RegInfo->hasFP(Fn)) { 440 int SFI = RS->getScavengingFrameIndex(); 441 if (SFI >= 0) { 442 // If stack grows down, we need to add size of find the lowest 443 // address of the object. 444 if (StackGrowsDown) 445 Offset += FFI->getObjectSize(SFI); 446 447 unsigned Align = FFI->getObjectAlignment(SFI); 448 // Adjust to alignment boundary 449 Offset = (Offset+Align-1)/Align*Align; 450 451 if (StackGrowsDown) { 452 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset 453 } else { 454 FFI->setObjectOffset(SFI, Offset); 455 Offset += FFI->getObjectSize(SFI); 456 } 457 } 458 } 459 460 // Round up the size to a multiple of the alignment, but only if there are 461 // calls or alloca's in the function. This ensures that any calls to 462 // subroutines have their stack frames suitable aligned. 463 if (!RegInfo->targetHandlesStackFrameRounding() && 464 (FFI->hasCalls() || FFI->hasVarSizedObjects())) { 465 // If we have reserved argument space for call sites in the function 466 // immediately on entry to the current function, count it as part of the 467 // overall stack size. 468 if (RegInfo->hasReservedCallFrame(Fn)) 469 Offset += FFI->getMaxCallFrameSize(); 470 471 unsigned AlignMask = TFI.getStackAlignment() - 1; 472 Offset = (Offset + AlignMask) & ~uint64_t(AlignMask); 473 } 474 475 // Update frame info to pretend that this is part of the stack... 476 FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea()); 477 478 // Remember the required stack alignment in case targets need it to perform 479 // dynamic stack alignment. 480 assert(FFI->getMaxAlignment() == MaxAlign && 481 "Stack alignment calculation broken!"); 482} 483 484 485/// insertPrologEpilogCode - Scan the function for modified callee saved 486/// registers, insert spill code for these callee saved registers, then add 487/// prolog and epilog code to the function. 488/// 489void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 490 // Add prologue to the function... 491 Fn.getTarget().getRegisterInfo()->emitPrologue(Fn); 492 493 // Add epilogue to restore the callee-save registers in each exiting block 494 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 495 // If last instruction is a return instruction, add an epilogue 496 if (!I->empty() && I->back().getDesc().isReturn()) 497 Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I); 498 } 499} 500 501 502/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 503/// register references and actual offsets. 504/// 505void PEI::replaceFrameIndices(MachineFunction &Fn) { 506 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 507 508 const TargetMachine &TM = Fn.getTarget(); 509 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 510 const MRegisterInfo &MRI = *TM.getRegisterInfo(); 511 const TargetFrameInfo *TFI = TM.getFrameInfo(); 512 bool StackGrowsDown = 513 TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown; 514 int FrameSetupOpcode = MRI.getCallFrameSetupOpcode(); 515 int FrameDestroyOpcode = MRI.getCallFrameDestroyOpcode(); 516 517 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 518 int SPAdj = 0; // SP offset due to call frame setup / destroy. 519 if (RS) RS->enterBasicBlock(BB); 520 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 521 MachineInstr *MI = I; 522 523 // Remember how much SP has been adjustment to create the call frame. 524 if (I->getOpcode() == FrameSetupOpcode || 525 I->getOpcode() == FrameDestroyOpcode) { 526 int Size = I->getOperand(0).getImm(); 527 if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) || 528 (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode)) 529 Size = -Size; 530 SPAdj += Size; 531 MachineBasicBlock::iterator PrevI = prior(I); 532 MRI.eliminateCallFramePseudoInstr(Fn, *BB, I); 533 // Visit the instructions created by eliminateCallFramePseudoInstr(). 534 I = next(PrevI); 535 MI = NULL; 536 } else { 537 I++; 538 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) 539 if (MI->getOperand(i).isFrameIndex()) { 540 // If this instruction has a FrameIndex operand, we need to use that 541 // target machine register info object to eliminate it. 542 MRI.eliminateFrameIndex(MI, SPAdj, RS); 543 544 // Revisit the instruction in full. Some instructions (e.g. inline 545 // asm instructions) can have multiple frame indices. 546 --I; 547 MI = 0; 548 break; 549 } 550 } 551 // Update register states. 552 if (RS && MI) RS->forward(MI); 553 } 554 assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?"); 555 } 556} 557