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