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