PrologEpilogInserter.cpp revision d2eae62e93fc6e398263a952609b6ea60a204802
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 bool *PhysRegsUsed = Fn.getUsedPhysregs(); 160 const TargetRegisterClass* const *CSRegClasses = 161 RegInfo->getCalleeSavedRegClasses(); 162 std::vector<CalleeSavedInfo> CSI; 163 for (unsigned i = 0; CSRegs[i]; ++i) { 164 unsigned Reg = CSRegs[i]; 165 if (PhysRegsUsed[Reg]) { 166 // If the reg is modified, save it! 167 CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i])); 168 } else { 169 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 170 *AliasSet; ++AliasSet) { // Check alias registers too. 171 if (PhysRegsUsed[*AliasSet]) { 172 CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i])); 173 break; 174 } 175 } 176 } 177 } 178 179 if (CSI.empty()) 180 return; // Early exit if no callee saved registers are modified! 181 182 unsigned NumFixedSpillSlots; 183 const std::pair<unsigned,int> *FixedSpillSlots = 184 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots); 185 186 // Now that we know which registers need to be saved and restored, allocate 187 // stack slots for them. 188 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 189 unsigned Reg = CSI[i].getReg(); 190 const TargetRegisterClass *RC = CSI[i].getRegClass(); 191 192 // Check to see if this physreg must be spilled to a particular stack slot 193 // on this target. 194 const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots; 195 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots && 196 FixedSlot->first != Reg) 197 ++FixedSlot; 198 199 int FrameIdx; 200 if (FixedSlot == FixedSpillSlots+NumFixedSpillSlots) { 201 // Nope, just spill it anywhere convenient. 202 unsigned Align = RC->getAlignment(); 203 unsigned StackAlign = TFI->getStackAlignment(); 204 // We may not be able to sastify the desired alignment specification of 205 // the TargetRegisterClass if the stack alignment is smaller. Use the min. 206 Align = std::min(Align, StackAlign); 207 FrameIdx = FFI->CreateStackObject(RC->getSize(), Align); 208 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx; 209 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx; 210 } else { 211 // Spill it to the stack where we must. 212 FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second); 213 } 214 CSI[i].setFrameIdx(FrameIdx); 215 } 216 217 FFI->setCalleeSavedInfo(CSI); 218} 219 220/// saveCalleeSavedRegisters - Insert spill code for any callee saved registers 221/// that are modified in the function. 222/// 223void PEI::saveCalleeSavedRegisters(MachineFunction &Fn) { 224 // Get callee saved register information. 225 MachineFrameInfo *FFI = Fn.getFrameInfo(); 226 const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo(); 227 228 // Early exit if no callee saved registers are modified! 229 if (CSI.empty()) 230 return; 231 232 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 233 234 // Now that we have a stack slot for each register to be saved, insert spill 235 // code into the entry block. 236 MachineBasicBlock *MBB = Fn.begin(); 237 MachineBasicBlock::iterator I = MBB->begin(); 238 if (!RegInfo->spillCalleeSavedRegisters(*MBB, I, CSI)) { 239 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 240 // Add the callee-saved register as live-in. It's killed at the spill. 241 MBB->addLiveIn(CSI[i].getReg()); 242 243 // Insert the spill to the stack frame. 244 RegInfo->storeRegToStackSlot(*MBB, I, CSI[i].getReg(), 245 CSI[i].getFrameIdx(), CSI[i].getRegClass()); 246 } 247 } 248 249 // Add code to restore the callee-save registers in each exiting block. 250 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 251 for (MachineFunction::iterator FI = Fn.begin(), E = Fn.end(); FI != E; ++FI) 252 // If last instruction is a return instruction, add an epilogue. 253 if (!FI->empty() && TII.isReturn(FI->back().getOpcode())) { 254 MBB = FI; 255 I = MBB->end(); --I; 256 257 // Skip over all terminator instructions, which are part of the return 258 // sequence. 259 MachineBasicBlock::iterator I2 = I; 260 while (I2 != MBB->begin() && TII.isTerminatorInstr((--I2)->getOpcode())) 261 I = I2; 262 263 bool AtStart = I == MBB->begin(); 264 MachineBasicBlock::iterator BeforeI = I; 265 if (!AtStart) 266 --BeforeI; 267 268 // Restore all registers immediately before the return and any terminators 269 // that preceed it. 270 if (!RegInfo->restoreCalleeSavedRegisters(*MBB, I, CSI)) { 271 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 272 RegInfo->loadRegFromStackSlot(*MBB, I, CSI[i].getReg(), 273 CSI[i].getFrameIdx(), 274 CSI[i].getRegClass()); 275 assert(I != MBB->begin() && 276 "loadRegFromStackSlot didn't insert any code!"); 277 // Insert in reverse order. loadRegFromStackSlot can insert multiple 278 // instructions. 279 if (AtStart) 280 I = MBB->begin(); 281 else { 282 I = BeforeI; 283 ++I; 284 } 285 } 286 } 287 } 288} 289 290 291/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 292/// abstract stack objects. 293/// 294void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 295 const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo(); 296 297 bool StackGrowsDown = 298 TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown; 299 300 // Loop over all of the stack objects, assigning sequential addresses... 301 MachineFrameInfo *FFI = Fn.getFrameInfo(); 302 303 unsigned MaxAlign = 0; 304 305 // Start at the beginning of the local area. 306 // The Offset is the distance from the stack top in the direction 307 // of stack growth -- so it's always positive. 308 int Offset = TFI.getOffsetOfLocalArea(); 309 if (StackGrowsDown) 310 Offset = -Offset; 311 assert(Offset >= 0 312 && "Local area offset should be in direction of stack growth"); 313 314 // If there are fixed sized objects that are preallocated in the local area, 315 // non-fixed objects can't be allocated right at the start of local area. 316 // We currently don't support filling in holes in between fixed sized objects, 317 // so we adjust 'Offset' to point to the end of last fixed sized 318 // preallocated object. 319 for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) { 320 int FixedOff; 321 if (StackGrowsDown) { 322 // The maximum distance from the stack pointer is at lower address of 323 // the object -- which is given by offset. For down growing stack 324 // the offset is negative, so we negate the offset to get the distance. 325 FixedOff = -FFI->getObjectOffset(i); 326 } else { 327 // The maximum distance from the start pointer is at the upper 328 // address of the object. 329 FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i); 330 } 331 if (FixedOff > Offset) Offset = FixedOff; 332 } 333 334 // First assign frame offsets to stack objects that are used to spill 335 // callee saved registers. 336 if (StackGrowsDown) { 337 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) { 338 if (i < MinCSFrameIndex || i > MaxCSFrameIndex) 339 continue; 340 341 // If stack grows down, we need to add size of find the lowest 342 // address of the object. 343 Offset += FFI->getObjectSize(i); 344 345 unsigned Align = FFI->getObjectAlignment(i); 346 // If the alignment of this object is greater than that of the stack, then 347 // increase the stack alignment to match. 348 MaxAlign = std::max(MaxAlign, Align); 349 // Adjust to alignment boundary 350 Offset = (Offset+Align-1)/Align*Align; 351 352 FFI->setObjectOffset(i, -Offset); // Set the computed offset 353 } 354 } else { 355 for (int i = FFI->getObjectIndexEnd()-1; i >= 0; --i) { 356 if ((unsigned)i < MinCSFrameIndex || (unsigned)i > MaxCSFrameIndex) 357 continue; 358 359 unsigned Align = FFI->getObjectAlignment(i); 360 // If the alignment of this object is greater than that of the stack, then 361 // increase the stack alignment to match. 362 MaxAlign = std::max(MaxAlign, Align); 363 // Adjust to alignment boundary 364 Offset = (Offset+Align-1)/Align*Align; 365 366 FFI->setObjectOffset(i, Offset); 367 Offset += FFI->getObjectSize(i); 368 } 369 } 370 371 // Make sure the special register scavenging spill slot is closest to the 372 // frame pointer if a frame pointer is required. 373 const MRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 374 if (RS && RegInfo->hasFP(Fn)) { 375 int SFI = RS->getScavengingFrameIndex(); 376 if (SFI >= 0) { 377 // If stack grows down, we need to add size of find the lowest 378 // address of the object. 379 if (StackGrowsDown) 380 Offset += FFI->getObjectSize(SFI); 381 382 unsigned Align = FFI->getObjectAlignment(SFI); 383 // Adjust to alignment boundary 384 Offset = (Offset+Align-1)/Align*Align; 385 386 if (StackGrowsDown) { 387 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset 388 } else { 389 FFI->setObjectOffset(SFI, Offset); 390 Offset += FFI->getObjectSize(SFI); 391 } 392 } 393 } 394 395 // Then assign frame offsets to stack objects that are not used to spill 396 // callee saved registers. 397 for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) { 398 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 399 continue; 400 if (RS && (int)i == RS->getScavengingFrameIndex()) 401 continue; 402 403 // If stack grows down, we need to add size of find the lowest 404 // address of the object. 405 if (StackGrowsDown) 406 Offset += FFI->getObjectSize(i); 407 408 unsigned Align = FFI->getObjectAlignment(i); 409 // If the alignment of this object is greater than that of the stack, then 410 // increase the stack alignment to match. 411 MaxAlign = std::max(MaxAlign, Align); 412 // Adjust to alignment boundary 413 Offset = (Offset+Align-1)/Align*Align; 414 415 if (StackGrowsDown) { 416 FFI->setObjectOffset(i, -Offset); // Set the computed offset 417 } else { 418 FFI->setObjectOffset(i, Offset); 419 Offset += FFI->getObjectSize(i); 420 } 421 } 422 423 // Make sure the special register scavenging spill slot is closest to the 424 // stack pointer. 425 if (RS) { 426 int SFI = RS->getScavengingFrameIndex(); 427 if (SFI >= 0) { 428 // If stack grows down, we need to add size of find the lowest 429 // address of the object. 430 if (StackGrowsDown) 431 Offset += FFI->getObjectSize(SFI); 432 433 unsigned Align = FFI->getObjectAlignment(SFI); 434 // Adjust to alignment boundary 435 Offset = (Offset+Align-1)/Align*Align; 436 437 if (StackGrowsDown) { 438 FFI->setObjectOffset(SFI, -Offset); // Set the computed offset 439 } else { 440 FFI->setObjectOffset(SFI, Offset); 441 Offset += FFI->getObjectSize(SFI); 442 } 443 } 444 } 445 446 // Round up the size to a multiple of the alignment, but only if there are 447 // calls or alloca's in the function. This ensures that any calls to 448 // subroutines have their stack frames suitable aligned. 449 if (!RegInfo->targetHandlesStackFrameRounding() && 450 (FFI->hasCalls() || FFI->hasVarSizedObjects())) { 451 // When we have no frame pointer, we reserve argument space for call sites 452 // in the function immediately on entry to the current function. This 453 // eliminates the need for add/sub sp brackets around call sites. 454 if (!RegInfo->hasFP(Fn)) 455 Offset += FFI->getMaxCallFrameSize(); 456 457 unsigned AlignMask = TFI.getStackAlignment() - 1; 458 Offset = (Offset + AlignMask) & ~AlignMask; 459 } 460 461 // Update frame info to pretend that this is part of the stack... 462 FFI->setStackSize(Offset+TFI.getOffsetOfLocalArea()); 463 464 // Remember the required stack alignment in case targets need it to perform 465 // dynamic stack alignment. 466 assert(FFI->getMaxAlignment() == MaxAlign && 467 "Stack alignment calculation broken!"); 468} 469 470 471/// insertPrologEpilogCode - Scan the function for modified callee saved 472/// registers, insert spill code for these callee saved registers, then add 473/// prolog and epilog code to the function. 474/// 475void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 476 // Add prologue to the function... 477 Fn.getTarget().getRegisterInfo()->emitPrologue(Fn); 478 479 // Add epilogue to restore the callee-save registers in each exiting block 480 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 481 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 482 // If last instruction is a return instruction, add an epilogue 483 if (!I->empty() && TII.isReturn(I->back().getOpcode())) 484 Fn.getTarget().getRegisterInfo()->emitEpilogue(Fn, *I); 485 } 486} 487 488 489/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 490/// register references and actual offsets. 491/// 492void PEI::replaceFrameIndices(MachineFunction &Fn) { 493 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 494 495 const TargetMachine &TM = Fn.getTarget(); 496 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 497 const MRegisterInfo &MRI = *TM.getRegisterInfo(); 498 499 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 500 if (RS) RS->enterBasicBlock(BB); 501 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 502 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 503 if (I->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(I, RS); 507 508 // Revisit the instruction in full. Some instructions (e.g. inline 509 // asm instructions) can have multiple frame indices. 510 e = I->getNumOperands(); 511 i = -1U; 512 } 513 // Update register states. 514 if (RS) RS->forward(I); 515 } 516 } 517} 518