PrologEpilogInserter.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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#define DEBUG_TYPE "pei" 20#include "PrologEpilogInserter.h" 21#include "llvm/ADT/IndexedMap.h" 22#include "llvm/ADT/STLExtras.h" 23#include "llvm/ADT/SetVector.h" 24#include "llvm/ADT/SmallSet.h" 25#include "llvm/ADT/Statistic.h" 26#include "llvm/CodeGen/MachineDominators.h" 27#include "llvm/CodeGen/MachineFrameInfo.h" 28#include "llvm/CodeGen/MachineInstr.h" 29#include "llvm/CodeGen/MachineLoopInfo.h" 30#include "llvm/CodeGen/MachineModuleInfo.h" 31#include "llvm/CodeGen/MachineRegisterInfo.h" 32#include "llvm/CodeGen/RegisterScavenging.h" 33#include "llvm/CodeGen/StackProtector.h" 34#include "llvm/IR/DiagnosticInfo.h" 35#include "llvm/IR/InlineAsm.h" 36#include "llvm/IR/LLVMContext.h" 37#include "llvm/Support/CommandLine.h" 38#include "llvm/Support/Compiler.h" 39#include "llvm/Support/Debug.h" 40#include "llvm/Support/raw_ostream.h" 41#include "llvm/Target/TargetFrameLowering.h" 42#include "llvm/Target/TargetInstrInfo.h" 43#include "llvm/Target/TargetMachine.h" 44#include "llvm/Target/TargetRegisterInfo.h" 45#include <climits> 46 47using namespace llvm; 48 49char PEI::ID = 0; 50char &llvm::PrologEpilogCodeInserterID = PEI::ID; 51 52static cl::opt<unsigned> 53WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1), 54 cl::desc("Warn for stack size bigger than the given" 55 " number")); 56 57INITIALIZE_PASS_BEGIN(PEI, "prologepilog", 58 "Prologue/Epilogue Insertion", false, false) 59INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 60INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 61INITIALIZE_PASS_DEPENDENCY(StackProtector) 62INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 63INITIALIZE_PASS_END(PEI, "prologepilog", 64 "Prologue/Epilogue Insertion & Frame Finalization", 65 false, false) 66 67STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged"); 68STATISTIC(NumBytesStackSpace, 69 "Number of bytes used for stack in all functions"); 70 71void PEI::getAnalysisUsage(AnalysisUsage &AU) const { 72 AU.setPreservesCFG(); 73 AU.addPreserved<MachineLoopInfo>(); 74 AU.addPreserved<MachineDominatorTree>(); 75 AU.addRequired<StackProtector>(); 76 AU.addRequired<TargetPassConfig>(); 77 MachineFunctionPass::getAnalysisUsage(AU); 78} 79 80bool PEI::isReturnBlock(MachineBasicBlock* MBB) { 81 return (MBB && !MBB->empty() && MBB->back().isReturn()); 82} 83 84/// Compute the set of return blocks 85void PEI::calculateSets(MachineFunction &Fn) { 86 // Sets used to compute spill, restore placement sets. 87 const std::vector<CalleeSavedInfo> &CSI = 88 Fn.getFrameInfo()->getCalleeSavedInfo(); 89 90 // If no CSRs used, we are done. 91 if (CSI.empty()) 92 return; 93 94 // Save refs to entry and return blocks. 95 EntryBlock = Fn.begin(); 96 for (MachineFunction::iterator MBB = Fn.begin(), E = Fn.end(); 97 MBB != E; ++MBB) 98 if (isReturnBlock(MBB)) 99 ReturnBlocks.push_back(MBB); 100 101 return; 102} 103 104/// StackObjSet - A set of stack object indexes 105typedef SmallSetVector<int, 8> StackObjSet; 106 107/// runOnMachineFunction - Insert prolog/epilog code and replace abstract 108/// frame indexes with appropriate references. 109/// 110bool PEI::runOnMachineFunction(MachineFunction &Fn) { 111 const Function* F = Fn.getFunction(); 112 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 113 const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering(); 114 115 assert(!Fn.getRegInfo().getNumVirtRegs() && "Regalloc must assign all vregs"); 116 117 RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL; 118 FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn); 119 120 // Calculate the MaxCallFrameSize and AdjustsStack variables for the 121 // function's frame information. Also eliminates call frame pseudo 122 // instructions. 123 calculateCallsInformation(Fn); 124 125 // Allow the target machine to make some adjustments to the function 126 // e.g. UsedPhysRegs before calculateCalleeSavedRegisters. 127 TFI->processFunctionBeforeCalleeSavedScan(Fn, RS); 128 129 // Scan the function for modified callee saved registers and insert spill code 130 // for any callee saved registers that are modified. 131 calculateCalleeSavedRegisters(Fn); 132 133 // Determine placement of CSR spill/restore code: 134 // place all spills in the entry block, all restores in return blocks. 135 calculateSets(Fn); 136 137 // Add the code to save and restore the callee saved registers 138 if (!F->hasFnAttribute(Attribute::Naked)) 139 insertCSRSpillsAndRestores(Fn); 140 141 // Allow the target machine to make final modifications to the function 142 // before the frame layout is finalized. 143 TFI->processFunctionBeforeFrameFinalized(Fn, RS); 144 145 // Calculate actual frame offsets for all abstract stack objects... 146 calculateFrameObjectOffsets(Fn); 147 148 // Add prolog and epilog code to the function. This function is required 149 // to align the stack frame as necessary for any stack variables or 150 // called functions. Because of this, calculateCalleeSavedRegisters() 151 // must be called before this function in order to set the AdjustsStack 152 // and MaxCallFrameSize variables. 153 if (!F->hasFnAttribute(Attribute::Naked)) 154 insertPrologEpilogCode(Fn); 155 156 // Replace all MO_FrameIndex operands with physical register references 157 // and actual offsets. 158 // 159 replaceFrameIndices(Fn); 160 161 // If register scavenging is needed, as we've enabled doing it as a 162 // post-pass, scavenge the virtual registers that frame index elimiation 163 // inserted. 164 if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging) 165 scavengeFrameVirtualRegs(Fn); 166 167 // Clear any vregs created by virtual scavenging. 168 Fn.getRegInfo().clearVirtRegs(); 169 170 // Warn on stack size when we exceeds the given limit. 171 MachineFrameInfo *MFI = Fn.getFrameInfo(); 172 uint64_t StackSize = MFI->getStackSize(); 173 if (WarnStackSize.getNumOccurrences() > 0 && WarnStackSize < StackSize) { 174 DiagnosticInfoStackSize DiagStackSize(*F, StackSize); 175 F->getContext().diagnose(DiagStackSize); 176 } 177 178 delete RS; 179 ReturnBlocks.clear(); 180 return true; 181} 182 183/// calculateCallsInformation - Calculate the MaxCallFrameSize and AdjustsStack 184/// variables for the function's frame information and eliminate call frame 185/// pseudo instructions. 186void PEI::calculateCallsInformation(MachineFunction &Fn) { 187 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 188 const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering(); 189 MachineFrameInfo *MFI = Fn.getFrameInfo(); 190 191 unsigned MaxCallFrameSize = 0; 192 bool AdjustsStack = MFI->adjustsStack(); 193 194 // Get the function call frame set-up and tear-down instruction opcode 195 int FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 196 int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 197 198 // Early exit for targets which have no call frame setup/destroy pseudo 199 // instructions. 200 if (FrameSetupOpcode == -1 && FrameDestroyOpcode == -1) 201 return; 202 203 std::vector<MachineBasicBlock::iterator> FrameSDOps; 204 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) 205 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) 206 if (I->getOpcode() == FrameSetupOpcode || 207 I->getOpcode() == FrameDestroyOpcode) { 208 assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo" 209 " instructions should have a single immediate argument!"); 210 unsigned Size = I->getOperand(0).getImm(); 211 if (Size > MaxCallFrameSize) MaxCallFrameSize = Size; 212 AdjustsStack = true; 213 FrameSDOps.push_back(I); 214 } else if (I->isInlineAsm()) { 215 // Some inline asm's need a stack frame, as indicated by operand 1. 216 unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm(); 217 if (ExtraInfo & InlineAsm::Extra_IsAlignStack) 218 AdjustsStack = true; 219 } 220 221 MFI->setAdjustsStack(AdjustsStack); 222 MFI->setMaxCallFrameSize(MaxCallFrameSize); 223 224 for (std::vector<MachineBasicBlock::iterator>::iterator 225 i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) { 226 MachineBasicBlock::iterator I = *i; 227 228 // If call frames are not being included as part of the stack frame, and 229 // the target doesn't indicate otherwise, remove the call frame pseudos 230 // here. The sub/add sp instruction pairs are still inserted, but we don't 231 // need to track the SP adjustment for frame index elimination. 232 if (TFI->canSimplifyCallFramePseudos(Fn)) 233 TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I); 234 } 235} 236 237 238/// calculateCalleeSavedRegisters - Scan the function for modified callee saved 239/// registers. 240void PEI::calculateCalleeSavedRegisters(MachineFunction &F) { 241 const TargetRegisterInfo *RegInfo = F.getTarget().getRegisterInfo(); 242 const TargetFrameLowering *TFI = F.getTarget().getFrameLowering(); 243 MachineFrameInfo *MFI = F.getFrameInfo(); 244 245 // Get the callee saved register list... 246 const uint16_t *CSRegs = RegInfo->getCalleeSavedRegs(&F); 247 248 // These are used to keep track the callee-save area. Initialize them. 249 MinCSFrameIndex = INT_MAX; 250 MaxCSFrameIndex = 0; 251 252 // Early exit for targets which have no callee saved registers. 253 if (CSRegs == 0 || CSRegs[0] == 0) 254 return; 255 256 // In Naked functions we aren't going to save any registers. 257 if (F.getFunction()->hasFnAttribute(Attribute::Naked)) 258 return; 259 260 std::vector<CalleeSavedInfo> CSI; 261 for (unsigned i = 0; CSRegs[i]; ++i) { 262 unsigned Reg = CSRegs[i]; 263 // Functions which call __builtin_unwind_init get all their registers saved. 264 if (F.getRegInfo().isPhysRegUsed(Reg) || F.getMMI().callsUnwindInit()) { 265 // If the reg is modified, save it! 266 CSI.push_back(CalleeSavedInfo(Reg)); 267 } 268 } 269 270 if (CSI.empty()) 271 return; // Early exit if no callee saved registers are modified! 272 273 unsigned NumFixedSpillSlots; 274 const TargetFrameLowering::SpillSlot *FixedSpillSlots = 275 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots); 276 277 // Now that we know which registers need to be saved and restored, allocate 278 // stack slots for them. 279 for (std::vector<CalleeSavedInfo>::iterator 280 I = CSI.begin(), E = CSI.end(); I != E; ++I) { 281 unsigned Reg = I->getReg(); 282 const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg); 283 284 int FrameIdx; 285 if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) { 286 I->setFrameIdx(FrameIdx); 287 continue; 288 } 289 290 // Check to see if this physreg must be spilled to a particular stack slot 291 // on this target. 292 const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots; 293 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots && 294 FixedSlot->Reg != Reg) 295 ++FixedSlot; 296 297 if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) { 298 // Nope, just spill it anywhere convenient. 299 unsigned Align = RC->getAlignment(); 300 unsigned StackAlign = TFI->getStackAlignment(); 301 302 // We may not be able to satisfy the desired alignment specification of 303 // the TargetRegisterClass if the stack alignment is smaller. Use the 304 // min. 305 Align = std::min(Align, StackAlign); 306 FrameIdx = MFI->CreateStackObject(RC->getSize(), Align, true); 307 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx; 308 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx; 309 } else { 310 // Spill it to the stack where we must. 311 FrameIdx = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset, true); 312 } 313 314 I->setFrameIdx(FrameIdx); 315 } 316 317 MFI->setCalleeSavedInfo(CSI); 318} 319 320/// insertCSRSpillsAndRestores - Insert spill and restore code for 321/// callee saved registers used in the function. 322/// 323void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) { 324 // Get callee saved register information. 325 MachineFrameInfo *MFI = Fn.getFrameInfo(); 326 const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo(); 327 328 MFI->setCalleeSavedInfoValid(true); 329 330 // Early exit if no callee saved registers are modified! 331 if (CSI.empty()) 332 return; 333 334 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 335 const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering(); 336 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 337 MachineBasicBlock::iterator I; 338 339 // Spill using target interface. 340 I = EntryBlock->begin(); 341 if (!TFI->spillCalleeSavedRegisters(*EntryBlock, I, CSI, TRI)) { 342 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 343 // Add the callee-saved register as live-in. 344 // It's killed at the spill. 345 EntryBlock->addLiveIn(CSI[i].getReg()); 346 347 // Insert the spill to the stack frame. 348 unsigned Reg = CSI[i].getReg(); 349 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); 350 TII.storeRegToStackSlot(*EntryBlock, I, Reg, true, CSI[i].getFrameIdx(), 351 RC, TRI); 352 } 353 } 354 355 // Restore using target interface. 356 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) { 357 MachineBasicBlock *MBB = ReturnBlocks[ri]; 358 I = MBB->end(); 359 --I; 360 361 // Skip over all terminator instructions, which are part of the return 362 // sequence. 363 MachineBasicBlock::iterator I2 = I; 364 while (I2 != MBB->begin() && (--I2)->isTerminator()) 365 I = I2; 366 367 bool AtStart = I == MBB->begin(); 368 MachineBasicBlock::iterator BeforeI = I; 369 if (!AtStart) 370 --BeforeI; 371 372 // Restore all registers immediately before the return and any 373 // terminators that precede it. 374 if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) { 375 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 376 unsigned Reg = CSI[i].getReg(); 377 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); 378 TII.loadRegFromStackSlot(*MBB, I, Reg, CSI[i].getFrameIdx(), RC, TRI); 379 assert(I != MBB->begin() && 380 "loadRegFromStackSlot didn't insert any code!"); 381 // Insert in reverse order. loadRegFromStackSlot can insert 382 // multiple instructions. 383 if (AtStart) 384 I = MBB->begin(); 385 else { 386 I = BeforeI; 387 ++I; 388 } 389 } 390 } 391 } 392} 393 394/// AdjustStackOffset - Helper function used to adjust the stack frame offset. 395static inline void 396AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, 397 bool StackGrowsDown, int64_t &Offset, 398 unsigned &MaxAlign) { 399 // If the stack grows down, add the object size to find the lowest address. 400 if (StackGrowsDown) 401 Offset += MFI->getObjectSize(FrameIdx); 402 403 unsigned Align = MFI->getObjectAlignment(FrameIdx); 404 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 409 // Adjust to alignment boundary. 410 Offset = (Offset + Align - 1) / Align * Align; 411 412 if (StackGrowsDown) { 413 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n"); 414 MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset 415 } else { 416 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n"); 417 MFI->setObjectOffset(FrameIdx, Offset); 418 Offset += MFI->getObjectSize(FrameIdx); 419 } 420} 421 422/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e., 423/// those required to be close to the Stack Protector) to stack offsets. 424static void 425AssignProtectedObjSet(const StackObjSet &UnassignedObjs, 426 SmallSet<int, 16> &ProtectedObjs, 427 MachineFrameInfo *MFI, bool StackGrowsDown, 428 int64_t &Offset, unsigned &MaxAlign) { 429 430 for (StackObjSet::const_iterator I = UnassignedObjs.begin(), 431 E = UnassignedObjs.end(); I != E; ++I) { 432 int i = *I; 433 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign); 434 ProtectedObjs.insert(i); 435 } 436} 437 438/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 439/// abstract stack objects. 440/// 441void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 442 const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); 443 StackProtector *SP = &getAnalysis<StackProtector>(); 444 445 bool StackGrowsDown = 446 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 447 448 // Loop over all of the stack objects, assigning sequential addresses... 449 MachineFrameInfo *MFI = Fn.getFrameInfo(); 450 451 // Start at the beginning of the local area. 452 // The Offset is the distance from the stack top in the direction 453 // of stack growth -- so it's always nonnegative. 454 int LocalAreaOffset = TFI.getOffsetOfLocalArea(); 455 if (StackGrowsDown) 456 LocalAreaOffset = -LocalAreaOffset; 457 assert(LocalAreaOffset >= 0 458 && "Local area offset should be in direction of stack growth"); 459 int64_t Offset = LocalAreaOffset; 460 461 // If there are fixed sized objects that are preallocated in the local area, 462 // non-fixed objects can't be allocated right at the start of local area. 463 // We currently don't support filling in holes in between fixed sized 464 // objects, so we adjust 'Offset' to point to the end of last fixed sized 465 // preallocated object. 466 for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) { 467 int64_t FixedOff; 468 if (StackGrowsDown) { 469 // The maximum distance from the stack pointer is at lower address of 470 // the object -- which is given by offset. For down growing stack 471 // the offset is negative, so we negate the offset to get the distance. 472 FixedOff = -MFI->getObjectOffset(i); 473 } else { 474 // The maximum distance from the start pointer is at the upper 475 // address of the object. 476 FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i); 477 } 478 if (FixedOff > Offset) Offset = FixedOff; 479 } 480 481 // First assign frame offsets to stack objects that are used to spill 482 // callee saved registers. 483 if (StackGrowsDown) { 484 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) { 485 // If the stack grows down, we need to add the size to find the lowest 486 // address of the object. 487 Offset += MFI->getObjectSize(i); 488 489 unsigned Align = MFI->getObjectAlignment(i); 490 // Adjust to alignment boundary 491 Offset = (Offset+Align-1)/Align*Align; 492 493 MFI->setObjectOffset(i, -Offset); // Set the computed offset 494 } 495 } else { 496 int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex; 497 for (int i = MaxCSFI; i >= MinCSFI ; --i) { 498 unsigned Align = MFI->getObjectAlignment(i); 499 // Adjust to alignment boundary 500 Offset = (Offset+Align-1)/Align*Align; 501 502 MFI->setObjectOffset(i, Offset); 503 Offset += MFI->getObjectSize(i); 504 } 505 } 506 507 unsigned MaxAlign = MFI->getMaxAlignment(); 508 509 // Make sure the special register scavenging spill slot is closest to the 510 // incoming stack pointer if a frame pointer is required and is closer 511 // to the incoming rather than the final stack pointer. 512 const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 513 bool EarlyScavengingSlots = (TFI.hasFP(Fn) && 514 TFI.isFPCloseToIncomingSP() && 515 RegInfo->useFPForScavengingIndex(Fn) && 516 !RegInfo->needsStackRealignment(Fn)); 517 if (RS && EarlyScavengingSlots) { 518 SmallVector<int, 2> SFIs; 519 RS->getScavengingFrameIndices(SFIs); 520 for (SmallVectorImpl<int>::iterator I = SFIs.begin(), 521 IE = SFIs.end(); I != IE; ++I) 522 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign); 523 } 524 525 // FIXME: Once this is working, then enable flag will change to a target 526 // check for whether the frame is large enough to want to use virtual 527 // frame index registers. Functions which don't want/need this optimization 528 // will continue to use the existing code path. 529 if (MFI->getUseLocalStackAllocationBlock()) { 530 unsigned Align = MFI->getLocalFrameMaxAlign(); 531 532 // Adjust to alignment boundary. 533 Offset = (Offset + Align - 1) / Align * Align; 534 535 DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n"); 536 537 // Resolve offsets for objects in the local block. 538 for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) { 539 std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i); 540 int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second; 541 DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << 542 FIOffset << "]\n"); 543 MFI->setObjectOffset(Entry.first, FIOffset); 544 } 545 // Allocate the local block 546 Offset += MFI->getLocalFrameSize(); 547 548 MaxAlign = std::max(Align, MaxAlign); 549 } 550 551 // Make sure that the stack protector comes before the local variables on the 552 // stack. 553 SmallSet<int, 16> ProtectedObjs; 554 if (MFI->getStackProtectorIndex() >= 0) { 555 StackObjSet LargeArrayObjs; 556 StackObjSet SmallArrayObjs; 557 StackObjSet AddrOfObjs; 558 559 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown, 560 Offset, MaxAlign); 561 562 // Assign large stack objects first. 563 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 564 if (MFI->isObjectPreAllocated(i) && 565 MFI->getUseLocalStackAllocationBlock()) 566 continue; 567 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 568 continue; 569 if (RS && RS->isScavengingFrameIndex((int)i)) 570 continue; 571 if (MFI->isDeadObjectIndex(i)) 572 continue; 573 if (MFI->getStackProtectorIndex() == (int)i) 574 continue; 575 576 switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) { 577 case StackProtector::SSPLK_None: 578 continue; 579 case StackProtector::SSPLK_SmallArray: 580 SmallArrayObjs.insert(i); 581 continue; 582 case StackProtector::SSPLK_AddrOf: 583 AddrOfObjs.insert(i); 584 continue; 585 case StackProtector::SSPLK_LargeArray: 586 LargeArrayObjs.insert(i); 587 continue; 588 } 589 llvm_unreachable("Unexpected SSPLayoutKind."); 590 } 591 592 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 593 Offset, MaxAlign); 594 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 595 Offset, MaxAlign); 596 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, 597 Offset, MaxAlign); 598 } 599 600 // Then assign frame offsets to stack objects that are not used to spill 601 // callee saved registers. 602 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 603 if (MFI->isObjectPreAllocated(i) && 604 MFI->getUseLocalStackAllocationBlock()) 605 continue; 606 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 607 continue; 608 if (RS && RS->isScavengingFrameIndex((int)i)) 609 continue; 610 if (MFI->isDeadObjectIndex(i)) 611 continue; 612 if (MFI->getStackProtectorIndex() == (int)i) 613 continue; 614 if (ProtectedObjs.count(i)) 615 continue; 616 617 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign); 618 } 619 620 // Make sure the special register scavenging spill slot is closest to the 621 // stack pointer. 622 if (RS && !EarlyScavengingSlots) { 623 SmallVector<int, 2> SFIs; 624 RS->getScavengingFrameIndices(SFIs); 625 for (SmallVectorImpl<int>::iterator I = SFIs.begin(), 626 IE = SFIs.end(); I != IE; ++I) 627 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign); 628 } 629 630 if (!TFI.targetHandlesStackFrameRounding()) { 631 // If we have reserved argument space for call sites in the function 632 // immediately on entry to the current function, count it as part of the 633 // overall stack size. 634 if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn)) 635 Offset += MFI->getMaxCallFrameSize(); 636 637 // Round up the size to a multiple of the alignment. If the function has 638 // any calls or alloca's, align to the target's StackAlignment value to 639 // ensure that the callee's frame or the alloca data is suitably aligned; 640 // otherwise, for leaf functions, align to the TransientStackAlignment 641 // value. 642 unsigned StackAlign; 643 if (MFI->adjustsStack() || MFI->hasVarSizedObjects() || 644 (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0)) 645 StackAlign = TFI.getStackAlignment(); 646 else 647 StackAlign = TFI.getTransientStackAlignment(); 648 649 // If the frame pointer is eliminated, all frame offsets will be relative to 650 // SP not FP. Align to MaxAlign so this works. 651 StackAlign = std::max(StackAlign, MaxAlign); 652 unsigned AlignMask = StackAlign - 1; 653 Offset = (Offset + AlignMask) & ~uint64_t(AlignMask); 654 } 655 656 // Update frame info to pretend that this is part of the stack... 657 int64_t StackSize = Offset - LocalAreaOffset; 658 MFI->setStackSize(StackSize); 659 NumBytesStackSpace += StackSize; 660} 661 662/// insertPrologEpilogCode - Scan the function for modified callee saved 663/// registers, insert spill code for these callee saved registers, then add 664/// prolog and epilog code to the function. 665/// 666void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 667 const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); 668 669 // Add prologue to the function... 670 TFI.emitPrologue(Fn); 671 672 // Add epilogue to restore the callee-save registers in each exiting block 673 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 674 // If last instruction is a return instruction, add an epilogue 675 if (!I->empty() && I->back().isReturn()) 676 TFI.emitEpilogue(Fn, *I); 677 } 678 679 // Emit additional code that is required to support segmented stacks, if 680 // we've been asked for it. This, when linked with a runtime with support 681 // for segmented stacks (libgcc is one), will result in allocating stack 682 // space in small chunks instead of one large contiguous block. 683 if (Fn.getTarget().Options.EnableSegmentedStacks) 684 TFI.adjustForSegmentedStacks(Fn); 685 686 // Emit additional code that is required to explicitly handle the stack in 687 // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The 688 // approach is rather similar to that of Segmented Stacks, but it uses a 689 // different conditional check and another BIF for allocating more stack 690 // space. 691 if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE) 692 TFI.adjustForHiPEPrologue(Fn); 693} 694 695/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 696/// register references and actual offsets. 697/// 698void PEI::replaceFrameIndices(MachineFunction &Fn) { 699 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 700 701 // Store SPAdj at exit of a basic block. 702 SmallVector<int, 8> SPState; 703 SPState.resize(Fn.getNumBlockIDs()); 704 SmallPtrSet<MachineBasicBlock*, 8> Reachable; 705 706 // Iterate over the reachable blocks in DFS order. 707 for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 708 DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable); 709 DFI != DFE; ++DFI) { 710 int SPAdj = 0; 711 // Check the exit state of the DFS stack predecessor. 712 if (DFI.getPathLength() >= 2) { 713 MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); 714 assert(Reachable.count(StackPred) && 715 "DFS stack predecessor is already visited.\n"); 716 SPAdj = SPState[StackPred->getNumber()]; 717 } 718 MachineBasicBlock *BB = *DFI; 719 replaceFrameIndices(BB, Fn, SPAdj); 720 SPState[BB->getNumber()] = SPAdj; 721 } 722 723 // Handle the unreachable blocks. 724 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 725 if (Reachable.count(BB)) 726 // Already handled in DFS traversal. 727 continue; 728 int SPAdj = 0; 729 replaceFrameIndices(BB, Fn, SPAdj); 730 } 731} 732 733void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn, 734 int &SPAdj) { 735 const TargetMachine &TM = Fn.getTarget(); 736 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 737 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 738 const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 739 const TargetFrameLowering *TFI = TM.getFrameLowering(); 740 bool StackGrowsDown = 741 TFI->getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 742 int FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 743 int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 744 745 if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB); 746 747 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 748 749 if (I->getOpcode() == FrameSetupOpcode || 750 I->getOpcode() == FrameDestroyOpcode) { 751 // Remember how much SP has been adjusted to create the call 752 // frame. 753 int Size = I->getOperand(0).getImm(); 754 755 if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) || 756 (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode)) 757 Size = -Size; 758 759 SPAdj += Size; 760 761 MachineBasicBlock::iterator PrevI = BB->end(); 762 if (I != BB->begin()) PrevI = std::prev(I); 763 TFI->eliminateCallFramePseudoInstr(Fn, *BB, I); 764 765 // Visit the instructions created by eliminateCallFramePseudoInstr(). 766 if (PrevI == BB->end()) 767 I = BB->begin(); // The replaced instr was the first in the block. 768 else 769 I = std::next(PrevI); 770 continue; 771 } 772 773 MachineInstr *MI = I; 774 bool DoIncr = true; 775 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 776 if (!MI->getOperand(i).isFI()) 777 continue; 778 779 // Frame indicies in debug values are encoded in a target independent 780 // way with simply the frame index and offset rather than any 781 // target-specific addressing mode. 782 if (MI->isDebugValue()) { 783 assert(i == 0 && "Frame indicies can only appear as the first " 784 "operand of a DBG_VALUE machine instruction"); 785 unsigned Reg; 786 MachineOperand &Offset = MI->getOperand(1); 787 Offset.setImm(Offset.getImm() + 788 TFI->getFrameIndexReference( 789 Fn, MI->getOperand(0).getIndex(), Reg)); 790 MI->getOperand(0).ChangeToRegister(Reg, false /*isDef*/); 791 continue; 792 } 793 794 // Some instructions (e.g. inline asm instructions) can have 795 // multiple frame indices and/or cause eliminateFrameIndex 796 // to insert more than one instruction. We need the register 797 // scavenger to go through all of these instructions so that 798 // it can update its register information. We keep the 799 // iterator at the point before insertion so that we can 800 // revisit them in full. 801 bool AtBeginning = (I == BB->begin()); 802 if (!AtBeginning) --I; 803 804 // If this instruction has a FrameIndex operand, we need to 805 // use that target machine register info object to eliminate 806 // it. 807 TRI.eliminateFrameIndex(MI, SPAdj, i, 808 FrameIndexVirtualScavenging ? NULL : RS); 809 810 // Reset the iterator if we were at the beginning of the BB. 811 if (AtBeginning) { 812 I = BB->begin(); 813 DoIncr = false; 814 } 815 816 MI = 0; 817 break; 818 } 819 820 if (DoIncr && I != BB->end()) ++I; 821 822 // Update register states. 823 if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI); 824 } 825} 826 827/// scavengeFrameVirtualRegs - Replace all frame index virtual registers 828/// with physical registers. Use the register scavenger to find an 829/// appropriate register to use. 830/// 831/// FIXME: Iterating over the instruction stream is unnecessary. We can simply 832/// iterate over the vreg use list, which at this point only contains machine 833/// operands for which eliminateFrameIndex need a new scratch reg. 834void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) { 835 // Run through the instructions and find any virtual registers. 836 for (MachineFunction::iterator BB = Fn.begin(), 837 E = Fn.end(); BB != E; ++BB) { 838 RS->enterBasicBlock(BB); 839 840 int SPAdj = 0; 841 842 // The instruction stream may change in the loop, so check BB->end() 843 // directly. 844 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 845 // We might end up here again with a NULL iterator if we scavenged a 846 // register for which we inserted spill code for definition by what was 847 // originally the first instruction in BB. 848 if (I == MachineBasicBlock::iterator(NULL)) 849 I = BB->begin(); 850 851 MachineInstr *MI = I; 852 MachineBasicBlock::iterator J = std::next(I); 853 MachineBasicBlock::iterator P = 854 I == BB->begin() ? MachineBasicBlock::iterator(NULL) : std::prev(I); 855 856 // RS should process this instruction before we might scavenge at this 857 // location. This is because we might be replacing a virtual register 858 // defined by this instruction, and if so, registers killed by this 859 // instruction are available, and defined registers are not. 860 RS->forward(I); 861 862 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 863 if (MI->getOperand(i).isReg()) { 864 MachineOperand &MO = MI->getOperand(i); 865 unsigned Reg = MO.getReg(); 866 if (Reg == 0) 867 continue; 868 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 869 continue; 870 871 // When we first encounter a new virtual register, it 872 // must be a definition. 873 assert(MI->getOperand(i).isDef() && 874 "frame index virtual missing def!"); 875 // Scavenge a new scratch register 876 const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg); 877 unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj); 878 879 ++NumScavengedRegs; 880 881 // Replace this reference to the virtual register with the 882 // scratch register. 883 assert (ScratchReg && "Missing scratch register!"); 884 Fn.getRegInfo().replaceRegWith(Reg, ScratchReg); 885 886 // Because this instruction was processed by the RS before this 887 // register was allocated, make sure that the RS now records the 888 // register as being used. 889 RS->setUsed(ScratchReg); 890 } 891 } 892 893 // If the scavenger needed to use one of its spill slots, the 894 // spill code will have been inserted in between I and J. This is a 895 // problem because we need the spill code before I: Move I to just 896 // prior to J. 897 if (I != std::prev(J)) { 898 BB->splice(J, BB, I); 899 900 // Before we move I, we need to prepare the RS to visit I again. 901 // Specifically, RS will assert if it sees uses of registers that 902 // it believes are undefined. Because we have already processed 903 // register kills in I, when it visits I again, it will believe that 904 // those registers are undefined. To avoid this situation, unprocess 905 // the instruction I. 906 assert(RS->getCurrentPosition() == I && 907 "The register scavenger has an unexpected position"); 908 I = P; 909 RS->unprocess(P); 910 } else 911 ++I; 912 } 913 } 914} 915