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