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