PrologEpilogInserter.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
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 elimiation 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 (CSI.empty()) 272 return; // Early exit if no callee saved registers are modified! 273 274 unsigned NumFixedSpillSlots; 275 const TargetFrameLowering::SpillSlot *FixedSpillSlots = 276 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots); 277 278 // Now that we know which registers need to be saved and restored, allocate 279 // stack slots for them. 280 for (std::vector<CalleeSavedInfo>::iterator 281 I = CSI.begin(), E = CSI.end(); I != E; ++I) { 282 unsigned Reg = I->getReg(); 283 const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg); 284 285 int FrameIdx; 286 if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) { 287 I->setFrameIdx(FrameIdx); 288 continue; 289 } 290 291 // Check to see if this physreg must be spilled to a particular stack slot 292 // on this target. 293 const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots; 294 while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots && 295 FixedSlot->Reg != Reg) 296 ++FixedSlot; 297 298 if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) { 299 // Nope, just spill it anywhere convenient. 300 unsigned Align = RC->getAlignment(); 301 unsigned StackAlign = TFI->getStackAlignment(); 302 303 // We may not be able to satisfy the desired alignment specification of 304 // the TargetRegisterClass if the stack alignment is smaller. Use the 305 // min. 306 Align = std::min(Align, StackAlign); 307 FrameIdx = MFI->CreateStackObject(RC->getSize(), Align, true); 308 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx; 309 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx; 310 } else { 311 // Spill it to the stack where we must. 312 FrameIdx = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset, true); 313 } 314 315 I->setFrameIdx(FrameIdx); 316 } 317 318 MFI->setCalleeSavedInfo(CSI); 319} 320 321/// insertCSRSpillsAndRestores - Insert spill and restore code for 322/// callee saved registers used in the function. 323/// 324void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) { 325 // Get callee saved register information. 326 MachineFrameInfo *MFI = Fn.getFrameInfo(); 327 const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo(); 328 329 MFI->setCalleeSavedInfoValid(true); 330 331 // Early exit if no callee saved registers are modified! 332 if (CSI.empty()) 333 return; 334 335 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 336 const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering(); 337 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 338 MachineBasicBlock::iterator I; 339 340 // Spill using target interface. 341 I = EntryBlock->begin(); 342 if (!TFI->spillCalleeSavedRegisters(*EntryBlock, I, CSI, TRI)) { 343 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 344 // Add the callee-saved register as live-in. 345 // It's killed at the spill. 346 EntryBlock->addLiveIn(CSI[i].getReg()); 347 348 // Insert the spill to the stack frame. 349 unsigned Reg = CSI[i].getReg(); 350 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); 351 TII.storeRegToStackSlot(*EntryBlock, I, Reg, true, CSI[i].getFrameIdx(), 352 RC, TRI); 353 } 354 } 355 356 // Restore using target interface. 357 for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) { 358 MachineBasicBlock *MBB = ReturnBlocks[ri]; 359 I = MBB->end(); 360 --I; 361 362 // Skip over all terminator instructions, which are part of the return 363 // sequence. 364 MachineBasicBlock::iterator I2 = I; 365 while (I2 != MBB->begin() && (--I2)->isTerminator()) 366 I = I2; 367 368 bool AtStart = I == MBB->begin(); 369 MachineBasicBlock::iterator BeforeI = I; 370 if (!AtStart) 371 --BeforeI; 372 373 // Restore all registers immediately before the return and any 374 // terminators that precede it. 375 if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) { 376 for (unsigned i = 0, e = CSI.size(); i != e; ++i) { 377 unsigned Reg = CSI[i].getReg(); 378 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg); 379 TII.loadRegFromStackSlot(*MBB, I, Reg, CSI[i].getFrameIdx(), RC, TRI); 380 assert(I != MBB->begin() && 381 "loadRegFromStackSlot didn't insert any code!"); 382 // Insert in reverse order. loadRegFromStackSlot can insert 383 // multiple instructions. 384 if (AtStart) 385 I = MBB->begin(); 386 else { 387 I = BeforeI; 388 ++I; 389 } 390 } 391 } 392 } 393} 394 395/// AdjustStackOffset - Helper function used to adjust the stack frame offset. 396static inline void 397AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, 398 bool StackGrowsDown, int64_t &Offset, 399 unsigned &MaxAlign) { 400 // If the stack grows down, add the object size to find the lowest address. 401 if (StackGrowsDown) 402 Offset += MFI->getObjectSize(FrameIdx); 403 404 unsigned Align = MFI->getObjectAlignment(FrameIdx); 405 406 // If the alignment of this object is greater than that of the stack, then 407 // increase the stack alignment to match. 408 MaxAlign = std::max(MaxAlign, Align); 409 410 // Adjust to alignment boundary. 411 Offset = (Offset + Align - 1) / Align * Align; 412 413 if (StackGrowsDown) { 414 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n"); 415 MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset 416 } else { 417 DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n"); 418 MFI->setObjectOffset(FrameIdx, Offset); 419 Offset += MFI->getObjectSize(FrameIdx); 420 } 421} 422 423/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e., 424/// those required to be close to the Stack Protector) to stack offsets. 425static void 426AssignProtectedObjSet(const StackObjSet &UnassignedObjs, 427 SmallSet<int, 16> &ProtectedObjs, 428 MachineFrameInfo *MFI, bool StackGrowsDown, 429 int64_t &Offset, unsigned &MaxAlign) { 430 431 for (StackObjSet::const_iterator I = UnassignedObjs.begin(), 432 E = UnassignedObjs.end(); I != E; ++I) { 433 int i = *I; 434 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign); 435 ProtectedObjs.insert(i); 436 } 437} 438 439/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 440/// abstract stack objects. 441/// 442void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) { 443 const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); 444 StackProtector *SP = &getAnalysis<StackProtector>(); 445 446 bool StackGrowsDown = 447 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 448 449 // Loop over all of the stack objects, assigning sequential addresses... 450 MachineFrameInfo *MFI = Fn.getFrameInfo(); 451 452 // Start at the beginning of the local area. 453 // The Offset is the distance from the stack top in the direction 454 // of stack growth -- so it's always nonnegative. 455 int LocalAreaOffset = TFI.getOffsetOfLocalArea(); 456 if (StackGrowsDown) 457 LocalAreaOffset = -LocalAreaOffset; 458 assert(LocalAreaOffset >= 0 459 && "Local area offset should be in direction of stack growth"); 460 int64_t Offset = LocalAreaOffset; 461 462 // If there are fixed sized objects that are preallocated in the local area, 463 // non-fixed objects can't be allocated right at the start of local area. 464 // We currently don't support filling in holes in between fixed sized 465 // objects, so we adjust 'Offset' to point to the end of last fixed sized 466 // preallocated object. 467 for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) { 468 int64_t FixedOff; 469 if (StackGrowsDown) { 470 // The maximum distance from the stack pointer is at lower address of 471 // the object -- which is given by offset. For down growing stack 472 // the offset is negative, so we negate the offset to get the distance. 473 FixedOff = -MFI->getObjectOffset(i); 474 } else { 475 // The maximum distance from the start pointer is at the upper 476 // address of the object. 477 FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i); 478 } 479 if (FixedOff > Offset) Offset = FixedOff; 480 } 481 482 // First assign frame offsets to stack objects that are used to spill 483 // callee saved registers. 484 if (StackGrowsDown) { 485 for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) { 486 // If the stack grows down, we need to add the size to find the lowest 487 // address of the object. 488 Offset += MFI->getObjectSize(i); 489 490 unsigned Align = MFI->getObjectAlignment(i); 491 // Adjust to alignment boundary 492 Offset = (Offset+Align-1)/Align*Align; 493 494 MFI->setObjectOffset(i, -Offset); // Set the computed offset 495 } 496 } else { 497 int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex; 498 for (int i = MaxCSFI; i >= MinCSFI ; --i) { 499 unsigned Align = MFI->getObjectAlignment(i); 500 // Adjust to alignment boundary 501 Offset = (Offset+Align-1)/Align*Align; 502 503 MFI->setObjectOffset(i, Offset); 504 Offset += MFI->getObjectSize(i); 505 } 506 } 507 508 unsigned MaxAlign = MFI->getMaxAlignment(); 509 510 // Make sure the special register scavenging spill slot is closest to the 511 // incoming stack pointer if a frame pointer is required and is closer 512 // to the incoming rather than the final stack pointer. 513 const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo(); 514 bool EarlyScavengingSlots = (TFI.hasFP(Fn) && 515 TFI.isFPCloseToIncomingSP() && 516 RegInfo->useFPForScavengingIndex(Fn) && 517 !RegInfo->needsStackRealignment(Fn)); 518 if (RS && EarlyScavengingSlots) { 519 SmallVector<int, 2> SFIs; 520 RS->getScavengingFrameIndices(SFIs); 521 for (SmallVectorImpl<int>::iterator I = SFIs.begin(), 522 IE = SFIs.end(); I != IE; ++I) 523 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign); 524 } 525 526 // FIXME: Once this is working, then enable flag will change to a target 527 // check for whether the frame is large enough to want to use virtual 528 // frame index registers. Functions which don't want/need this optimization 529 // will continue to use the existing code path. 530 if (MFI->getUseLocalStackAllocationBlock()) { 531 unsigned Align = MFI->getLocalFrameMaxAlign(); 532 533 // Adjust to alignment boundary. 534 Offset = (Offset + Align - 1) / Align * Align; 535 536 DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n"); 537 538 // Resolve offsets for objects in the local block. 539 for (unsigned i = 0, e = MFI->getLocalFrameObjectCount(); i != e; ++i) { 540 std::pair<int, int64_t> Entry = MFI->getLocalFrameObjectMap(i); 541 int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second; 542 DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << 543 FIOffset << "]\n"); 544 MFI->setObjectOffset(Entry.first, FIOffset); 545 } 546 // Allocate the local block 547 Offset += MFI->getLocalFrameSize(); 548 549 MaxAlign = std::max(Align, MaxAlign); 550 } 551 552 // Make sure that the stack protector comes before the local variables on the 553 // stack. 554 SmallSet<int, 16> ProtectedObjs; 555 if (MFI->getStackProtectorIndex() >= 0) { 556 StackObjSet LargeArrayObjs; 557 StackObjSet SmallArrayObjs; 558 StackObjSet AddrOfObjs; 559 560 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown, 561 Offset, MaxAlign); 562 563 // Assign large stack objects first. 564 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 565 if (MFI->isObjectPreAllocated(i) && 566 MFI->getUseLocalStackAllocationBlock()) 567 continue; 568 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 569 continue; 570 if (RS && RS->isScavengingFrameIndex((int)i)) 571 continue; 572 if (MFI->isDeadObjectIndex(i)) 573 continue; 574 if (MFI->getStackProtectorIndex() == (int)i) 575 continue; 576 577 switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) { 578 case StackProtector::SSPLK_None: 579 continue; 580 case StackProtector::SSPLK_SmallArray: 581 SmallArrayObjs.insert(i); 582 continue; 583 case StackProtector::SSPLK_AddrOf: 584 AddrOfObjs.insert(i); 585 continue; 586 case StackProtector::SSPLK_LargeArray: 587 LargeArrayObjs.insert(i); 588 continue; 589 } 590 llvm_unreachable("Unexpected SSPLayoutKind."); 591 } 592 593 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 594 Offset, MaxAlign); 595 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 596 Offset, MaxAlign); 597 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, 598 Offset, MaxAlign); 599 } 600 601 // Then assign frame offsets to stack objects that are not used to spill 602 // callee saved registers. 603 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 604 if (MFI->isObjectPreAllocated(i) && 605 MFI->getUseLocalStackAllocationBlock()) 606 continue; 607 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex) 608 continue; 609 if (RS && RS->isScavengingFrameIndex((int)i)) 610 continue; 611 if (MFI->isDeadObjectIndex(i)) 612 continue; 613 if (MFI->getStackProtectorIndex() == (int)i) 614 continue; 615 if (ProtectedObjs.count(i)) 616 continue; 617 618 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign); 619 } 620 621 // Make sure the special register scavenging spill slot is closest to the 622 // stack pointer. 623 if (RS && !EarlyScavengingSlots) { 624 SmallVector<int, 2> SFIs; 625 RS->getScavengingFrameIndices(SFIs); 626 for (SmallVectorImpl<int>::iterator I = SFIs.begin(), 627 IE = SFIs.end(); I != IE; ++I) 628 AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign); 629 } 630 631 if (!TFI.targetHandlesStackFrameRounding()) { 632 // If we have reserved argument space for call sites in the function 633 // immediately on entry to the current function, count it as part of the 634 // overall stack size. 635 if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn)) 636 Offset += MFI->getMaxCallFrameSize(); 637 638 // Round up the size to a multiple of the alignment. If the function has 639 // any calls or alloca's, align to the target's StackAlignment value to 640 // ensure that the callee's frame or the alloca data is suitably aligned; 641 // otherwise, for leaf functions, align to the TransientStackAlignment 642 // value. 643 unsigned StackAlign; 644 if (MFI->adjustsStack() || MFI->hasVarSizedObjects() || 645 (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0)) 646 StackAlign = TFI.getStackAlignment(); 647 else 648 StackAlign = TFI.getTransientStackAlignment(); 649 650 // If the frame pointer is eliminated, all frame offsets will be relative to 651 // SP not FP. Align to MaxAlign so this works. 652 StackAlign = std::max(StackAlign, MaxAlign); 653 unsigned AlignMask = StackAlign - 1; 654 Offset = (Offset + AlignMask) & ~uint64_t(AlignMask); 655 } 656 657 // Update frame info to pretend that this is part of the stack... 658 int64_t StackSize = Offset - LocalAreaOffset; 659 MFI->setStackSize(StackSize); 660 NumBytesStackSpace += StackSize; 661} 662 663/// insertPrologEpilogCode - Scan the function for modified callee saved 664/// registers, insert spill code for these callee saved registers, then add 665/// prolog and epilog code to the function. 666/// 667void PEI::insertPrologEpilogCode(MachineFunction &Fn) { 668 const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); 669 670 // Add prologue to the function... 671 TFI.emitPrologue(Fn); 672 673 // Add epilogue to restore the callee-save registers in each exiting block 674 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 675 // If last instruction is a return instruction, add an epilogue 676 if (!I->empty() && I->back().isReturn()) 677 TFI.emitEpilogue(Fn, *I); 678 } 679 680 // Emit additional code that is required to support segmented stacks, if 681 // we've been asked for it. This, when linked with a runtime with support 682 // for segmented stacks (libgcc is one), will result in allocating stack 683 // space in small chunks instead of one large contiguous block. 684 if (Fn.shouldSplitStack()) 685 TFI.adjustForSegmentedStacks(Fn); 686 687 // Emit additional code that is required to explicitly handle the stack in 688 // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The 689 // approach is rather similar to that of Segmented Stacks, but it uses a 690 // different conditional check and another BIF for allocating more stack 691 // space. 692 if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE) 693 TFI.adjustForHiPEPrologue(Fn); 694} 695 696/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical 697/// register references and actual offsets. 698/// 699void PEI::replaceFrameIndices(MachineFunction &Fn) { 700 if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do? 701 702 // Store SPAdj at exit of a basic block. 703 SmallVector<int, 8> SPState; 704 SPState.resize(Fn.getNumBlockIDs()); 705 SmallPtrSet<MachineBasicBlock*, 8> Reachable; 706 707 // Iterate over the reachable blocks in DFS order. 708 for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> > 709 DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable); 710 DFI != DFE; ++DFI) { 711 int SPAdj = 0; 712 // Check the exit state of the DFS stack predecessor. 713 if (DFI.getPathLength() >= 2) { 714 MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2); 715 assert(Reachable.count(StackPred) && 716 "DFS stack predecessor is already visited.\n"); 717 SPAdj = SPState[StackPred->getNumber()]; 718 } 719 MachineBasicBlock *BB = *DFI; 720 replaceFrameIndices(BB, Fn, SPAdj); 721 SPState[BB->getNumber()] = SPAdj; 722 } 723 724 // Handle the unreachable blocks. 725 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 726 if (Reachable.count(BB)) 727 // Already handled in DFS traversal. 728 continue; 729 int SPAdj = 0; 730 replaceFrameIndices(BB, Fn, SPAdj); 731 } 732} 733 734void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn, 735 int &SPAdj) { 736 const TargetMachine &TM = Fn.getTarget(); 737 assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!"); 738 const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo(); 739 const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 740 const TargetFrameLowering *TFI = TM.getFrameLowering(); 741 bool StackGrowsDown = 742 TFI->getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 743 int FrameSetupOpcode = TII.getCallFrameSetupOpcode(); 744 int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode(); 745 746 if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB); 747 748 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 749 750 if (I->getOpcode() == FrameSetupOpcode || 751 I->getOpcode() == FrameDestroyOpcode) { 752 // Remember how much SP has been adjusted to create the call 753 // frame. 754 int Size = I->getOperand(0).getImm(); 755 756 if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) || 757 (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode)) 758 Size = -Size; 759 760 SPAdj += Size; 761 762 MachineBasicBlock::iterator PrevI = BB->end(); 763 if (I != BB->begin()) PrevI = std::prev(I); 764 TFI->eliminateCallFramePseudoInstr(Fn, *BB, I); 765 766 // Visit the instructions created by eliminateCallFramePseudoInstr(). 767 if (PrevI == BB->end()) 768 I = BB->begin(); // The replaced instr was the first in the block. 769 else 770 I = std::next(PrevI); 771 continue; 772 } 773 774 MachineInstr *MI = I; 775 bool DoIncr = true; 776 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 777 if (!MI->getOperand(i).isFI()) 778 continue; 779 780 // Frame indicies in debug values are encoded in a target independent 781 // way with simply the frame index and offset rather than any 782 // target-specific addressing mode. 783 if (MI->isDebugValue()) { 784 assert(i == 0 && "Frame indicies can only appear as the first " 785 "operand of a DBG_VALUE machine instruction"); 786 unsigned Reg; 787 MachineOperand &Offset = MI->getOperand(1); 788 Offset.setImm(Offset.getImm() + 789 TFI->getFrameIndexReference( 790 Fn, MI->getOperand(0).getIndex(), Reg)); 791 MI->getOperand(0).ChangeToRegister(Reg, false /*isDef*/); 792 continue; 793 } 794 795 // Some instructions (e.g. inline asm instructions) can have 796 // multiple frame indices and/or cause eliminateFrameIndex 797 // to insert more than one instruction. We need the register 798 // scavenger to go through all of these instructions so that 799 // it can update its register information. We keep the 800 // iterator at the point before insertion so that we can 801 // revisit them in full. 802 bool AtBeginning = (I == BB->begin()); 803 if (!AtBeginning) --I; 804 805 // If this instruction has a FrameIndex operand, we need to 806 // use that target machine register info object to eliminate 807 // it. 808 TRI.eliminateFrameIndex(MI, SPAdj, i, 809 FrameIndexVirtualScavenging ? nullptr : RS); 810 811 // Reset the iterator if we were at the beginning of the BB. 812 if (AtBeginning) { 813 I = BB->begin(); 814 DoIncr = false; 815 } 816 817 MI = nullptr; 818 break; 819 } 820 821 if (DoIncr && I != BB->end()) ++I; 822 823 // Update register states. 824 if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI); 825 } 826} 827 828/// scavengeFrameVirtualRegs - Replace all frame index virtual registers 829/// with physical registers. Use the register scavenger to find an 830/// appropriate register to use. 831/// 832/// FIXME: Iterating over the instruction stream is unnecessary. We can simply 833/// iterate over the vreg use list, which at this point only contains machine 834/// operands for which eliminateFrameIndex need a new scratch reg. 835void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) { 836 // Run through the instructions and find any virtual registers. 837 for (MachineFunction::iterator BB = Fn.begin(), 838 E = Fn.end(); BB != E; ++BB) { 839 RS->enterBasicBlock(BB); 840 841 int SPAdj = 0; 842 843 // The instruction stream may change in the loop, so check BB->end() 844 // directly. 845 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) { 846 // We might end up here again with a NULL iterator if we scavenged a 847 // register for which we inserted spill code for definition by what was 848 // originally the first instruction in BB. 849 if (I == MachineBasicBlock::iterator(nullptr)) 850 I = BB->begin(); 851 852 MachineInstr *MI = I; 853 MachineBasicBlock::iterator J = std::next(I); 854 MachineBasicBlock::iterator P = 855 I == BB->begin() ? MachineBasicBlock::iterator(nullptr) 856 : std::prev(I); 857 858 // RS should process this instruction before we might scavenge at this 859 // location. This is because we might be replacing a virtual register 860 // defined by this instruction, and if so, registers killed by this 861 // instruction are available, and defined registers are not. 862 RS->forward(I); 863 864 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 865 if (MI->getOperand(i).isReg()) { 866 MachineOperand &MO = MI->getOperand(i); 867 unsigned Reg = MO.getReg(); 868 if (Reg == 0) 869 continue; 870 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 871 continue; 872 873 // When we first encounter a new virtual register, it 874 // must be a definition. 875 assert(MI->getOperand(i).isDef() && 876 "frame index virtual missing def!"); 877 // Scavenge a new scratch register 878 const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg); 879 unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj); 880 881 ++NumScavengedRegs; 882 883 // Replace this reference to the virtual register with the 884 // scratch register. 885 assert (ScratchReg && "Missing scratch register!"); 886 Fn.getRegInfo().replaceRegWith(Reg, ScratchReg); 887 888 // Because this instruction was processed by the RS before this 889 // register was allocated, make sure that the RS now records the 890 // register as being used. 891 RS->setUsed(ScratchReg); 892 } 893 } 894 895 // If the scavenger needed to use one of its spill slots, the 896 // spill code will have been inserted in between I and J. This is a 897 // problem because we need the spill code before I: Move I to just 898 // prior to J. 899 if (I != std::prev(J)) { 900 BB->splice(J, BB, I); 901 902 // Before we move I, we need to prepare the RS to visit I again. 903 // Specifically, RS will assert if it sees uses of registers that 904 // it believes are undefined. Because we have already processed 905 // register kills in I, when it visits I again, it will believe that 906 // those registers are undefined. To avoid this situation, unprocess 907 // the instruction I. 908 assert(RS->getCurrentPosition() == I && 909 "The register scavenger has an unexpected position"); 910 I = P; 911 RS->unprocess(P); 912 } else 913 ++I; 914 } 915 } 916} 917