1607 lines · cpp
1//===- PrologEpilogInserter.cpp - Insert Prolog/Epilog code in function ---===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass is responsible for finalizing the functions frame layout, saving10// callee saved registers, and for emitting prolog & epilog code for the11// function.12//13// This pass must be run after register allocation. After this pass is14// executed, it is illegal to construct MO_FrameIndex operands.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/ADT/ArrayRef.h"19#include "llvm/ADT/BitVector.h"20#include "llvm/ADT/STLExtras.h"21#include "llvm/ADT/SetVector.h"22#include "llvm/ADT/SmallPtrSet.h"23#include "llvm/ADT/SmallSet.h"24#include "llvm/ADT/SmallVector.h"25#include "llvm/ADT/Statistic.h"26#include "llvm/Analysis/OptimizationRemarkEmitter.h"27#include "llvm/CodeGen/MachineBasicBlock.h"28#include "llvm/CodeGen/MachineDominators.h"29#include "llvm/CodeGen/MachineFrameInfo.h"30#include "llvm/CodeGen/MachineFunction.h"31#include "llvm/CodeGen/MachineFunctionPass.h"32#include "llvm/CodeGen/MachineInstr.h"33#include "llvm/CodeGen/MachineLoopInfo.h"34#include "llvm/CodeGen/MachineModuleInfo.h"35#include "llvm/CodeGen/MachineOperand.h"36#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"37#include "llvm/CodeGen/MachineRegisterInfo.h"38#include "llvm/CodeGen/PEI.h"39#include "llvm/CodeGen/RegisterScavenging.h"40#include "llvm/CodeGen/TargetFrameLowering.h"41#include "llvm/CodeGen/TargetInstrInfo.h"42#include "llvm/CodeGen/TargetOpcodes.h"43#include "llvm/CodeGen/TargetRegisterInfo.h"44#include "llvm/CodeGen/TargetSubtargetInfo.h"45#include "llvm/CodeGen/WinEHFuncInfo.h"46#include "llvm/IR/Attributes.h"47#include "llvm/IR/CallingConv.h"48#include "llvm/IR/DebugInfoMetadata.h"49#include "llvm/IR/DiagnosticInfo.h"50#include "llvm/IR/Function.h"51#include "llvm/IR/LLVMContext.h"52#include "llvm/InitializePasses.h"53#include "llvm/Pass.h"54#include "llvm/Support/CodeGen.h"55#include "llvm/Support/Debug.h"56#include "llvm/Support/ErrorHandling.h"57#include "llvm/Support/FormatVariadic.h"58#include "llvm/Support/raw_ostream.h"59#include "llvm/Target/TargetMachine.h"60#include "llvm/Target/TargetOptions.h"61#include <algorithm>62#include <cassert>63#include <cstdint>64#include <limits>65#include <utility>66#include <vector>67 68using namespace llvm;69 70#define DEBUG_TYPE "prologepilog"71 72using MBBVector = SmallVector<MachineBasicBlock *, 4>;73 74STATISTIC(NumLeafFuncWithSpills, "Number of leaf functions with CSRs");75STATISTIC(NumFuncSeen, "Number of functions seen in PEI");76 77 78namespace {79 80class PEIImpl {81 RegScavenger *RS = nullptr;82 83 // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved84 // stack frame indexes.85 unsigned MinCSFrameIndex = std::numeric_limits<unsigned>::max();86 unsigned MaxCSFrameIndex = 0;87 88 // Save and Restore blocks of the current function. Typically there is a89 // single save block, unless Windows EH funclets are involved.90 MBBVector SaveBlocks;91 MBBVector RestoreBlocks;92 93 // Flag to control whether to use the register scavenger to resolve94 // frame index materialization registers. Set according to95 // TRI->requiresFrameIndexScavenging() for the current function.96 bool FrameIndexVirtualScavenging = false;97 98 // Flag to control whether the scavenger should be passed even though99 // FrameIndexVirtualScavenging is used.100 bool FrameIndexEliminationScavenging = false;101 102 // Emit remarks.103 MachineOptimizationRemarkEmitter *ORE = nullptr;104 105 void calculateCallFrameInfo(MachineFunction &MF);106 void calculateSaveRestoreBlocks(MachineFunction &MF);107 void spillCalleeSavedRegs(MachineFunction &MF);108 109 void calculateFrameObjectOffsets(MachineFunction &MF);110 void replaceFrameIndices(MachineFunction &MF);111 void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,112 int &SPAdj);113 // Frame indices in debug values are encoded in a target independent114 // way with simply the frame index and offset rather than any115 // target-specific addressing mode.116 bool replaceFrameIndexDebugInstr(MachineFunction &MF, MachineInstr &MI,117 unsigned OpIdx, int SPAdj = 0);118 // Does same as replaceFrameIndices but using the backward MIR walk and119 // backward register scavenger walk.120 void replaceFrameIndicesBackward(MachineFunction &MF);121 void replaceFrameIndicesBackward(MachineBasicBlock *BB, MachineFunction &MF,122 int &SPAdj);123 124 void insertPrologEpilogCode(MachineFunction &MF);125 void insertZeroCallUsedRegs(MachineFunction &MF);126 127public:128 PEIImpl(MachineOptimizationRemarkEmitter *ORE) : ORE(ORE) {}129 bool run(MachineFunction &MF);130};131 132class PEILegacy : public MachineFunctionPass {133public:134 static char ID;135 136 PEILegacy() : MachineFunctionPass(ID) {137 initializePEILegacyPass(*PassRegistry::getPassRegistry());138 }139 140 void getAnalysisUsage(AnalysisUsage &AU) const override;141 142 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract143 /// frame indexes with appropriate references.144 bool runOnMachineFunction(MachineFunction &MF) override;145};146 147} // end anonymous namespace148 149char PEILegacy::ID = 0;150 151char &llvm::PrologEpilogCodeInserterID = PEILegacy::ID;152 153INITIALIZE_PASS_BEGIN(PEILegacy, DEBUG_TYPE, "Prologue/Epilogue Insertion",154 false, false)155INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)156INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)157INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)158INITIALIZE_PASS_END(PEILegacy, DEBUG_TYPE,159 "Prologue/Epilogue Insertion & Frame Finalization", false,160 false)161 162MachineFunctionPass *llvm::createPrologEpilogInserterPass() {163 return new PEILegacy();164}165 166STATISTIC(NumBytesStackSpace,167 "Number of bytes used for stack in all functions");168 169void PEILegacy::getAnalysisUsage(AnalysisUsage &AU) const {170 AU.setPreservesCFG();171 AU.addPreserved<MachineLoopInfoWrapperPass>();172 AU.addPreserved<MachineDominatorTreeWrapperPass>();173 AU.addRequired<MachineOptimizationRemarkEmitterPass>();174 MachineFunctionPass::getAnalysisUsage(AU);175}176 177/// StackObjSet - A set of stack object indexes178using StackObjSet = SmallSetVector<int, 8>;179 180using SavedDbgValuesMap =181 SmallDenseMap<MachineBasicBlock *, SmallVector<MachineInstr *, 4>, 4>;182 183/// Stash DBG_VALUEs that describe parameters and which are placed at the start184/// of the block. Later on, after the prologue code has been emitted, the185/// stashed DBG_VALUEs will be reinserted at the start of the block.186static void stashEntryDbgValues(MachineBasicBlock &MBB,187 SavedDbgValuesMap &EntryDbgValues) {188 SmallVector<const MachineInstr *, 4> FrameIndexValues;189 190 for (auto &MI : MBB) {191 if (!MI.isDebugInstr())192 break;193 if (!MI.isDebugValue() || !MI.getDebugVariable()->isParameter())194 continue;195 if (any_of(MI.debug_operands(),196 [](const MachineOperand &MO) { return MO.isFI(); })) {197 // We can only emit valid locations for frame indices after the frame198 // setup, so do not stash away them.199 FrameIndexValues.push_back(&MI);200 continue;201 }202 const DILocalVariable *Var = MI.getDebugVariable();203 const DIExpression *Expr = MI.getDebugExpression();204 auto Overlaps = [Var, Expr](const MachineInstr *DV) {205 return Var == DV->getDebugVariable() &&206 Expr->fragmentsOverlap(DV->getDebugExpression());207 };208 // See if the debug value overlaps with any preceding debug value that will209 // not be stashed. If that is the case, then we can't stash this value, as210 // we would then reorder the values at reinsertion.211 if (llvm::none_of(FrameIndexValues, Overlaps))212 EntryDbgValues[&MBB].push_back(&MI);213 }214 215 // Remove stashed debug values from the block.216 if (auto It = EntryDbgValues.find(&MBB); It != EntryDbgValues.end())217 for (auto *MI : It->second)218 MI->removeFromParent();219}220 221bool PEIImpl::run(MachineFunction &MF) {222 NumFuncSeen++;223 const Function &F = MF.getFunction();224 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();225 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();226 227 RS = TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr;228 FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(MF);229 230 // Spill frame pointer and/or base pointer registers if they are clobbered.231 // It is placed before call frame instruction elimination so it will not mess232 // with stack arguments.233 TFI->spillFPBP(MF);234 235 // Calculate the MaxCallFrameSize value for the function's frame236 // information. Also eliminates call frame pseudo instructions.237 calculateCallFrameInfo(MF);238 239 // Determine placement of CSR spill/restore code and prolog/epilog code:240 // place all spills in the entry block, all restores in return blocks.241 calculateSaveRestoreBlocks(MF);242 243 // Stash away DBG_VALUEs that should not be moved by insertion of prolog code.244 SavedDbgValuesMap EntryDbgValues;245 for (MachineBasicBlock *SaveBlock : SaveBlocks)246 stashEntryDbgValues(*SaveBlock, EntryDbgValues);247 248 // Handle CSR spilling and restoring, for targets that need it.249 if (MF.getTarget().usesPhysRegsForValues())250 spillCalleeSavedRegs(MF);251 252 // Allow the target machine to make final modifications to the function253 // before the frame layout is finalized.254 TFI->processFunctionBeforeFrameFinalized(MF, RS);255 256 // Calculate actual frame offsets for all abstract stack objects...257 calculateFrameObjectOffsets(MF);258 259 // Add prolog and epilog code to the function. This function is required260 // to align the stack frame as necessary for any stack variables or261 // called functions. Because of this, calculateCalleeSavedRegisters()262 // must be called before this function in order to set the AdjustsStack263 // and MaxCallFrameSize variables.264 if (!F.hasFnAttribute(Attribute::Naked))265 insertPrologEpilogCode(MF);266 267 // Reinsert stashed debug values at the start of the entry blocks.268 for (auto &I : EntryDbgValues)269 I.first->insert(I.first->begin(), I.second.begin(), I.second.end());270 271 // Allow the target machine to make final modifications to the function272 // before the frame layout is finalized.273 TFI->processFunctionBeforeFrameIndicesReplaced(MF, RS);274 275 // Replace all MO_FrameIndex operands with physical register references276 // and actual offsets.277 if (TFI->needsFrameIndexResolution(MF)) {278 // Allow the target to determine this after knowing the frame size.279 FrameIndexEliminationScavenging =280 (RS && !FrameIndexVirtualScavenging) ||281 TRI->requiresFrameIndexReplacementScavenging(MF);282 283 if (TRI->eliminateFrameIndicesBackwards())284 replaceFrameIndicesBackward(MF);285 else286 replaceFrameIndices(MF);287 }288 289 // If register scavenging is needed, as we've enabled doing it as a290 // post-pass, scavenge the virtual registers that frame index elimination291 // inserted.292 if (TRI->requiresRegisterScavenging(MF) && FrameIndexVirtualScavenging)293 scavengeFrameVirtualRegs(MF, *RS);294 295 // Warn on stack size when we exceeds the given limit.296 MachineFrameInfo &MFI = MF.getFrameInfo();297 uint64_t StackSize = MFI.getStackSize();298 299 uint64_t Threshold = TFI->getStackThreshold();300 if (MF.getFunction().hasFnAttribute("warn-stack-size")) {301 bool Failed = MF.getFunction()302 .getFnAttribute("warn-stack-size")303 .getValueAsString()304 .getAsInteger(10, Threshold);305 // Verifier should have caught this.306 assert(!Failed && "Invalid warn-stack-size fn attr value");307 (void)Failed;308 }309 uint64_t UnsafeStackSize = MFI.getUnsafeStackSize();310 if (MF.getFunction().hasFnAttribute(Attribute::SafeStack))311 StackSize += UnsafeStackSize;312 313 if (StackSize > Threshold) {314 DiagnosticInfoStackSize DiagStackSize(F, StackSize, Threshold, DS_Warning);315 F.getContext().diagnose(DiagStackSize);316 int64_t SpillSize = 0;317 for (int Idx = MFI.getObjectIndexBegin(), End = MFI.getObjectIndexEnd();318 Idx != End; ++Idx) {319 if (MFI.isSpillSlotObjectIndex(Idx))320 SpillSize += MFI.getObjectSize(Idx);321 }322 323 [[maybe_unused]] float SpillPct =324 static_cast<float>(SpillSize) / static_cast<float>(StackSize);325 LLVM_DEBUG(326 dbgs() << formatv("{0}/{1} ({3:P}) spills, {2}/{1} ({4:P}) variables",327 SpillSize, StackSize, StackSize - SpillSize, SpillPct,328 1.0f - SpillPct));329 if (UnsafeStackSize != 0) {330 LLVM_DEBUG(dbgs() << formatv(", {0}/{2} ({1:P}) unsafe stack",331 UnsafeStackSize,332 static_cast<float>(UnsafeStackSize) /333 static_cast<float>(StackSize),334 StackSize));335 }336 LLVM_DEBUG(dbgs() << "\n");337 }338 339 ORE->emit([&]() {340 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "StackSize",341 MF.getFunction().getSubprogram(),342 &MF.front())343 << ore::NV("NumStackBytes", StackSize)344 << " stack bytes in function '"345 << ore::NV("Function", MF.getFunction().getName()) << "'";346 });347 348 // Emit any remarks implemented for the target, based on final frame layout.349 TFI->emitRemarks(MF, ORE);350 351 delete RS;352 SaveBlocks.clear();353 RestoreBlocks.clear();354 MFI.clearSavePoints();355 MFI.clearRestorePoints();356 return true;357}358 359/// runOnMachineFunction - Insert prolog/epilog code and replace abstract360/// frame indexes with appropriate references.361bool PEILegacy::runOnMachineFunction(MachineFunction &MF) {362 MachineOptimizationRemarkEmitter *ORE =363 &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();364 return PEIImpl(ORE).run(MF);365}366 367PreservedAnalyses368PrologEpilogInserterPass::run(MachineFunction &MF,369 MachineFunctionAnalysisManager &MFAM) {370 MachineOptimizationRemarkEmitter &ORE =371 MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(MF);372 if (!PEIImpl(&ORE).run(MF))373 return PreservedAnalyses::all();374 375 return getMachineFunctionPassPreservedAnalyses()376 .preserveSet<CFGAnalyses>()377 .preserve<MachineDominatorTreeAnalysis>()378 .preserve<MachineLoopAnalysis>();379}380 381/// Calculate the MaxCallFrameSize variable for the function's frame382/// information and eliminate call frame pseudo instructions.383void PEIImpl::calculateCallFrameInfo(MachineFunction &MF) {384 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();385 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();386 MachineFrameInfo &MFI = MF.getFrameInfo();387 388 // Get the function call frame set-up and tear-down instruction opcode389 unsigned FrameSetupOpcode = TII.getCallFrameSetupOpcode();390 unsigned FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();391 392 // Early exit for targets which have no call frame setup/destroy pseudo393 // instructions.394 if (FrameSetupOpcode == ~0u && FrameDestroyOpcode == ~0u)395 return;396 397 // (Re-)Compute the MaxCallFrameSize.398 [[maybe_unused]] uint64_t MaxCFSIn =399 MFI.isMaxCallFrameSizeComputed() ? MFI.getMaxCallFrameSize() : UINT64_MAX;400 std::vector<MachineBasicBlock::iterator> FrameSDOps;401 MFI.computeMaxCallFrameSize(MF, &FrameSDOps);402 assert(MFI.getMaxCallFrameSize() <= MaxCFSIn &&403 "Recomputing MaxCFS gave a larger value.");404 assert((FrameSDOps.empty() || MF.getFrameInfo().adjustsStack()) &&405 "AdjustsStack not set in presence of a frame pseudo instruction.");406 407 if (TFI->canSimplifyCallFramePseudos(MF)) {408 // If call frames are not being included as part of the stack frame, and409 // the target doesn't indicate otherwise, remove the call frame pseudos410 // here. The sub/add sp instruction pairs are still inserted, but we don't411 // need to track the SP adjustment for frame index elimination.412 for (MachineBasicBlock::iterator I : FrameSDOps)413 TFI->eliminateCallFramePseudoInstr(MF, *I->getParent(), I);414 415 // We can't track the call frame size after call frame pseudos have been416 // eliminated. Set it to zero everywhere to keep MachineVerifier happy.417 for (MachineBasicBlock &MBB : MF)418 MBB.setCallFrameSize(0);419 }420}421 422/// Compute the sets of entry and return blocks for saving and restoring423/// callee-saved registers, and placing prolog and epilog code.424void PEIImpl::calculateSaveRestoreBlocks(MachineFunction &MF) {425 const MachineFrameInfo &MFI = MF.getFrameInfo();426 // Even when we do not change any CSR, we still want to insert the427 // prologue and epilogue of the function.428 // So set the save points for those.429 430 // Use the points found by shrink-wrapping, if any.431 if (!MFI.getSavePoints().empty()) {432 assert(MFI.getSavePoints().size() == 1 &&433 "Multiple save points are not yet supported!");434 const auto &SavePoint = *MFI.getSavePoints().begin();435 SaveBlocks.push_back(SavePoint.first);436 assert(MFI.getRestorePoints().size() == 1 &&437 "Multiple restore points are not yet supported!");438 const auto &RestorePoint = *MFI.getRestorePoints().begin();439 MachineBasicBlock *RestoreBlock = RestorePoint.first;440 // If RestoreBlock does not have any successor and is not a return block441 // then the end point is unreachable and we do not need to insert any442 // epilogue.443 if (!RestoreBlock->succ_empty() || RestoreBlock->isReturnBlock())444 RestoreBlocks.push_back(RestoreBlock);445 return;446 }447 448 // Save refs to entry and return blocks.449 SaveBlocks.push_back(&MF.front());450 for (MachineBasicBlock &MBB : MF) {451 if (MBB.isEHFuncletEntry())452 SaveBlocks.push_back(&MBB);453 if (MBB.isReturnBlock())454 RestoreBlocks.push_back(&MBB);455 }456}457 458static void assignCalleeSavedSpillSlots(MachineFunction &F,459 const BitVector &SavedRegs,460 unsigned &MinCSFrameIndex,461 unsigned &MaxCSFrameIndex) {462 if (SavedRegs.empty())463 return;464 465 const TargetRegisterInfo *RegInfo = F.getSubtarget().getRegisterInfo();466 const MCPhysReg *CSRegs = F.getRegInfo().getCalleeSavedRegs();467 BitVector CSMask(SavedRegs.size());468 469 for (unsigned i = 0; CSRegs[i]; ++i)470 CSMask.set(CSRegs[i]);471 472 std::vector<CalleeSavedInfo> CSI;473 for (unsigned i = 0; CSRegs[i]; ++i) {474 unsigned Reg = CSRegs[i];475 if (SavedRegs.test(Reg)) {476 bool SavedSuper = false;477 for (const MCPhysReg &SuperReg : RegInfo->superregs(Reg)) {478 // Some backends set all aliases for some registers as saved, such as479 // Mips's $fp, so they appear in SavedRegs but not CSRegs.480 if (SavedRegs.test(SuperReg) && CSMask.test(SuperReg)) {481 SavedSuper = true;482 break;483 }484 }485 486 if (!SavedSuper)487 CSI.push_back(CalleeSavedInfo(Reg));488 }489 }490 491 const TargetFrameLowering *TFI = F.getSubtarget().getFrameLowering();492 MachineFrameInfo &MFI = F.getFrameInfo();493 if (!TFI->assignCalleeSavedSpillSlots(F, RegInfo, CSI, MinCSFrameIndex,494 MaxCSFrameIndex)) {495 // If target doesn't implement this, use generic code.496 497 if (CSI.empty())498 return; // Early exit if no callee saved registers are modified!499 500 unsigned NumFixedSpillSlots;501 const TargetFrameLowering::SpillSlot *FixedSpillSlots =502 TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);503 504 // Now that we know which registers need to be saved and restored, allocate505 // stack slots for them.506 for (auto &CS : CSI) {507 // If the target has spilled this register to another register or already508 // handled it , we don't need to allocate a stack slot.509 if (CS.isSpilledToReg())510 continue;511 512 MCRegister Reg = CS.getReg();513 const TargetRegisterClass *RC = RegInfo->getMinimalPhysRegClass(Reg);514 515 int FrameIdx;516 if (RegInfo->hasReservedSpillSlot(F, Reg, FrameIdx)) {517 CS.setFrameIdx(FrameIdx);518 continue;519 }520 521 // Check to see if this physreg must be spilled to a particular stack slot522 // on this target.523 const TargetFrameLowering::SpillSlot *FixedSlot = FixedSpillSlots;524 while (FixedSlot != FixedSpillSlots + NumFixedSpillSlots &&525 FixedSlot->Reg != Reg)526 ++FixedSlot;527 528 unsigned Size = RegInfo->getSpillSize(*RC);529 if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {530 // Nope, just spill it anywhere convenient.531 Align Alignment = RegInfo->getSpillAlign(*RC);532 // We may not be able to satisfy the desired alignment specification of533 // the TargetRegisterClass if the stack alignment is smaller. Use the534 // min.535 Alignment = std::min(Alignment, TFI->getStackAlign());536 FrameIdx = MFI.CreateStackObject(Size, Alignment, true);537 if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;538 if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;539 } else {540 // Spill it to the stack where we must.541 FrameIdx = MFI.CreateFixedSpillStackObject(Size, FixedSlot->Offset);542 }543 544 CS.setFrameIdx(FrameIdx);545 }546 }547 548 MFI.setCalleeSavedInfo(CSI);549}550 551/// Helper function to update the liveness information for the callee-saved552/// registers.553static void updateLiveness(MachineFunction &MF) {554 MachineFrameInfo &MFI = MF.getFrameInfo();555 // Visited will contain all the basic blocks that are in the region556 // where the callee saved registers are alive:557 // - Anything that is not Save or Restore -> LiveThrough.558 // - Save -> LiveIn.559 // - Restore -> LiveOut.560 // The live-out is not attached to the block, so no need to keep561 // Restore in this set.562 SmallPtrSet<MachineBasicBlock *, 8> Visited;563 SmallVector<MachineBasicBlock *, 8> WorkList;564 MachineBasicBlock *Entry = &MF.front();565 566 assert(MFI.getSavePoints().size() < 2 &&567 "Multiple save points not yet supported!");568 MachineBasicBlock *Save = MFI.getSavePoints().empty()569 ? nullptr570 : (*MFI.getSavePoints().begin()).first;571 572 if (!Save)573 Save = Entry;574 575 if (Entry != Save) {576 WorkList.push_back(Entry);577 Visited.insert(Entry);578 }579 Visited.insert(Save);580 581 assert(MFI.getRestorePoints().size() < 2 &&582 "Multiple restore points not yet supported!");583 MachineBasicBlock *Restore = MFI.getRestorePoints().empty()584 ? nullptr585 : (*MFI.getRestorePoints().begin()).first;586 if (Restore)587 // By construction Restore cannot be visited, otherwise it588 // means there exists a path to Restore that does not go589 // through Save.590 WorkList.push_back(Restore);591 592 while (!WorkList.empty()) {593 const MachineBasicBlock *CurBB = WorkList.pop_back_val();594 // By construction, the region that is after the save point is595 // dominated by the Save and post-dominated by the Restore.596 if (CurBB == Save && Save != Restore)597 continue;598 // Enqueue all the successors not already visited.599 // Those are by construction either before Save or after Restore.600 for (MachineBasicBlock *SuccBB : CurBB->successors())601 if (Visited.insert(SuccBB).second)602 WorkList.push_back(SuccBB);603 }604 605 const std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();606 607 MachineRegisterInfo &MRI = MF.getRegInfo();608 for (const CalleeSavedInfo &I : CSI) {609 for (MachineBasicBlock *MBB : Visited) {610 MCRegister Reg = I.getReg();611 // Add the callee-saved register as live-in.612 // It's killed at the spill.613 if (!MRI.isReserved(Reg) && !MBB->isLiveIn(Reg))614 MBB->addLiveIn(Reg);615 }616 // If callee-saved register is spilled to another register rather than617 // spilling to stack, the destination register has to be marked as live for618 // each MBB between the prologue and epilogue so that it is not clobbered619 // before it is reloaded in the epilogue. The Visited set contains all620 // blocks outside of the region delimited by prologue/epilogue.621 if (I.isSpilledToReg()) {622 for (MachineBasicBlock &MBB : MF) {623 if (Visited.count(&MBB))624 continue;625 MCRegister DstReg = I.getDstReg();626 if (!MBB.isLiveIn(DstReg))627 MBB.addLiveIn(DstReg);628 }629 }630 }631}632 633/// Insert spill code for the callee-saved registers used in the function.634static void insertCSRSaves(MachineBasicBlock &SaveBlock,635 ArrayRef<CalleeSavedInfo> CSI) {636 MachineFunction &MF = *SaveBlock.getParent();637 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();638 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();639 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();640 641 MachineBasicBlock::iterator I = SaveBlock.begin();642 if (!TFI->spillCalleeSavedRegisters(SaveBlock, I, CSI, TRI)) {643 for (const CalleeSavedInfo &CS : CSI) {644 TFI->spillCalleeSavedRegister(SaveBlock, I, CS, TII, TRI);645 }646 }647}648 649/// Insert restore code for the callee-saved registers used in the function.650static void insertCSRRestores(MachineBasicBlock &RestoreBlock,651 std::vector<CalleeSavedInfo> &CSI) {652 MachineFunction &MF = *RestoreBlock.getParent();653 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();654 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();655 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();656 657 // Restore all registers immediately before the return and any658 // terminators that precede it.659 MachineBasicBlock::iterator I = RestoreBlock.getFirstTerminator();660 661 if (!TFI->restoreCalleeSavedRegisters(RestoreBlock, I, CSI, TRI)) {662 for (const CalleeSavedInfo &CI : reverse(CSI)) {663 TFI->restoreCalleeSavedRegister(RestoreBlock, I, CI, TII, TRI);664 }665 }666}667 668void PEIImpl::spillCalleeSavedRegs(MachineFunction &MF) {669 // We can't list this requirement in getRequiredProperties because some670 // targets (WebAssembly) use virtual registers past this point, and the pass671 // pipeline is set up without giving the passes a chance to look at the672 // TargetMachine.673 // FIXME: Find a way to express this in getRequiredProperties.674 assert(MF.getProperties().hasNoVRegs());675 676 const Function &F = MF.getFunction();677 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();678 MachineFrameInfo &MFI = MF.getFrameInfo();679 MinCSFrameIndex = std::numeric_limits<unsigned>::max();680 MaxCSFrameIndex = 0;681 682 // Determine which of the registers in the callee save list should be saved.683 BitVector SavedRegs;684 TFI->determineCalleeSaves(MF, SavedRegs, RS);685 686 // Assign stack slots for any callee-saved registers that must be spilled.687 assignCalleeSavedSpillSlots(MF, SavedRegs, MinCSFrameIndex, MaxCSFrameIndex);688 689 // Add the code to save and restore the callee saved registers.690 if (!F.hasFnAttribute(Attribute::Naked)) {691 MFI.setCalleeSavedInfoValid(true);692 693 std::vector<CalleeSavedInfo> &CSI = MFI.getCalleeSavedInfo();694 695 // Fill SavePoints and RestorePoints with CalleeSavedRegisters696 if (!MFI.getSavePoints().empty()) {697 SaveRestorePoints SaveRestorePts;698 for (const auto &SavePoint : MFI.getSavePoints())699 SaveRestorePts.insert({SavePoint.first, CSI});700 MFI.setSavePoints(std::move(SaveRestorePts));701 702 SaveRestorePts.clear();703 for (const auto &RestorePoint : MFI.getRestorePoints())704 SaveRestorePts.insert({RestorePoint.first, CSI});705 MFI.setRestorePoints(std::move(SaveRestorePts));706 }707 708 if (!CSI.empty()) {709 if (!MFI.hasCalls())710 NumLeafFuncWithSpills++;711 712 for (MachineBasicBlock *SaveBlock : SaveBlocks)713 insertCSRSaves(*SaveBlock, CSI);714 715 // Update the live-in information of all the blocks up to the save point.716 updateLiveness(MF);717 718 for (MachineBasicBlock *RestoreBlock : RestoreBlocks)719 insertCSRRestores(*RestoreBlock, CSI);720 }721 }722}723 724/// AdjustStackOffset - Helper function used to adjust the stack frame offset.725static inline void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx,726 bool StackGrowsDown, int64_t &Offset,727 Align &MaxAlign) {728 // If the stack grows down, add the object size to find the lowest address.729 if (StackGrowsDown)730 Offset += MFI.getObjectSize(FrameIdx);731 732 Align Alignment = MFI.getObjectAlign(FrameIdx);733 734 // If the alignment of this object is greater than that of the stack, then735 // increase the stack alignment to match.736 MaxAlign = std::max(MaxAlign, Alignment);737 738 // Adjust to alignment boundary.739 Offset = alignTo(Offset, Alignment);740 741 if (StackGrowsDown) {742 LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset743 << "]\n");744 MFI.setObjectOffset(FrameIdx, -Offset); // Set the computed offset745 } else {746 LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset747 << "]\n");748 MFI.setObjectOffset(FrameIdx, Offset);749 Offset += MFI.getObjectSize(FrameIdx);750 }751}752 753/// Compute which bytes of fixed and callee-save stack area are unused and keep754/// track of them in StackBytesFree.755static inline void756computeFreeStackSlots(MachineFrameInfo &MFI, bool StackGrowsDown,757 unsigned MinCSFrameIndex, unsigned MaxCSFrameIndex,758 int64_t FixedCSEnd, BitVector &StackBytesFree) {759 // Avoid undefined int64_t -> int conversion below in extreme case.760 if (FixedCSEnd > std::numeric_limits<int>::max())761 return;762 763 StackBytesFree.resize(FixedCSEnd, true);764 765 SmallVector<int, 16> AllocatedFrameSlots;766 // Add fixed objects.767 for (int i = MFI.getObjectIndexBegin(); i != 0; ++i)768 // StackSlot scavenging is only implemented for the default stack.769 if (MFI.getStackID(i) == TargetStackID::Default)770 AllocatedFrameSlots.push_back(i);771 // Add callee-save objects if there are any.772 if (MinCSFrameIndex <= MaxCSFrameIndex) {773 for (int i = MinCSFrameIndex; i <= (int)MaxCSFrameIndex; ++i)774 if (MFI.getStackID(i) == TargetStackID::Default)775 AllocatedFrameSlots.push_back(i);776 }777 778 for (int i : AllocatedFrameSlots) {779 // These are converted from int64_t, but they should always fit in int780 // because of the FixedCSEnd check above.781 int ObjOffset = MFI.getObjectOffset(i);782 int ObjSize = MFI.getObjectSize(i);783 int ObjStart, ObjEnd;784 if (StackGrowsDown) {785 // ObjOffset is negative when StackGrowsDown is true.786 ObjStart = -ObjOffset - ObjSize;787 ObjEnd = -ObjOffset;788 } else {789 ObjStart = ObjOffset;790 ObjEnd = ObjOffset + ObjSize;791 }792 // Ignore fixed holes that are in the previous stack frame.793 if (ObjEnd > 0)794 StackBytesFree.reset(ObjStart, ObjEnd);795 }796}797 798/// Assign frame object to an unused portion of the stack in the fixed stack799/// object range. Return true if the allocation was successful.800static inline bool scavengeStackSlot(MachineFrameInfo &MFI, int FrameIdx,801 bool StackGrowsDown, Align MaxAlign,802 BitVector &StackBytesFree) {803 if (MFI.isVariableSizedObjectIndex(FrameIdx))804 return false;805 806 if (StackBytesFree.none()) {807 // clear it to speed up later scavengeStackSlot calls to808 // StackBytesFree.none()809 StackBytesFree.clear();810 return false;811 }812 813 Align ObjAlign = MFI.getObjectAlign(FrameIdx);814 if (ObjAlign > MaxAlign)815 return false;816 817 int64_t ObjSize = MFI.getObjectSize(FrameIdx);818 int FreeStart;819 for (FreeStart = StackBytesFree.find_first(); FreeStart != -1;820 FreeStart = StackBytesFree.find_next(FreeStart)) {821 822 // Check that free space has suitable alignment.823 unsigned ObjStart = StackGrowsDown ? FreeStart + ObjSize : FreeStart;824 if (alignTo(ObjStart, ObjAlign) != ObjStart)825 continue;826 827 if (FreeStart + ObjSize > StackBytesFree.size())828 return false;829 830 bool AllBytesFree = true;831 for (unsigned Byte = 0; Byte < ObjSize; ++Byte)832 if (!StackBytesFree.test(FreeStart + Byte)) {833 AllBytesFree = false;834 break;835 }836 if (AllBytesFree)837 break;838 }839 840 if (FreeStart == -1)841 return false;842 843 if (StackGrowsDown) {844 int ObjStart = -(FreeStart + ObjSize);845 LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["846 << ObjStart << "]\n");847 MFI.setObjectOffset(FrameIdx, ObjStart);848 } else {849 LLVM_DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") scavenged at SP["850 << FreeStart << "]\n");851 MFI.setObjectOffset(FrameIdx, FreeStart);852 }853 854 StackBytesFree.reset(FreeStart, FreeStart + ObjSize);855 return true;856}857 858/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,859/// those required to be close to the Stack Protector) to stack offsets.860static void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,861 SmallSet<int, 16> &ProtectedObjs,862 MachineFrameInfo &MFI, bool StackGrowsDown,863 int64_t &Offset, Align &MaxAlign) {864 865 for (int i : UnassignedObjs) {866 AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);867 ProtectedObjs.insert(i);868 }869}870 871/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the872/// abstract stack objects.873void PEIImpl::calculateFrameObjectOffsets(MachineFunction &MF) {874 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();875 876 bool StackGrowsDown =877 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;878 879 // Loop over all of the stack objects, assigning sequential addresses...880 MachineFrameInfo &MFI = MF.getFrameInfo();881 882 // Start at the beginning of the local area.883 // The Offset is the distance from the stack top in the direction884 // of stack growth -- so it's always nonnegative.885 int LocalAreaOffset = TFI.getOffsetOfLocalArea();886 if (StackGrowsDown)887 LocalAreaOffset = -LocalAreaOffset;888 assert(LocalAreaOffset >= 0889 && "Local area offset should be in direction of stack growth");890 int64_t Offset = LocalAreaOffset;891 892#ifdef EXPENSIVE_CHECKS893 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i)894 if (!MFI.isDeadObjectIndex(i) &&895 MFI.getStackID(i) == TargetStackID::Default)896 assert(MFI.getObjectAlign(i) <= MFI.getMaxAlign() &&897 "MaxAlignment is invalid");898#endif899 900 // If there are fixed sized objects that are preallocated in the local area,901 // non-fixed objects can't be allocated right at the start of local area.902 // Adjust 'Offset' to point to the end of last fixed sized preallocated903 // object.904 for (int i = MFI.getObjectIndexBegin(); i != 0; ++i) {905 // Only allocate objects on the default stack.906 if (MFI.getStackID(i) != TargetStackID::Default)907 continue;908 909 int64_t FixedOff;910 if (StackGrowsDown) {911 // The maximum distance from the stack pointer is at lower address of912 // the object -- which is given by offset. For down growing stack913 // the offset is negative, so we negate the offset to get the distance.914 FixedOff = -MFI.getObjectOffset(i);915 } else {916 // The maximum distance from the start pointer is at the upper917 // address of the object.918 FixedOff = MFI.getObjectOffset(i) + MFI.getObjectSize(i);919 }920 if (FixedOff > Offset) Offset = FixedOff;921 }922 923 Align MaxAlign = MFI.getMaxAlign();924 // First assign frame offsets to stack objects that are used to spill925 // callee saved registers.926 if (MaxCSFrameIndex >= MinCSFrameIndex) {927 for (unsigned i = 0; i <= MaxCSFrameIndex - MinCSFrameIndex; ++i) {928 unsigned FrameIndex =929 StackGrowsDown ? MinCSFrameIndex + i : MaxCSFrameIndex - i;930 931 // Only allocate objects on the default stack.932 if (MFI.getStackID(FrameIndex) != TargetStackID::Default)933 continue;934 935 // TODO: should this just be if (MFI.isDeadObjectIndex(FrameIndex))936 if (!StackGrowsDown && MFI.isDeadObjectIndex(FrameIndex))937 continue;938 939 AdjustStackOffset(MFI, FrameIndex, StackGrowsDown, Offset, MaxAlign);940 }941 }942 943 assert(MaxAlign == MFI.getMaxAlign() &&944 "MFI.getMaxAlign should already account for all callee-saved "945 "registers without a fixed stack slot");946 947 // FixedCSEnd is the stack offset to the end of the fixed and callee-save948 // stack area.949 int64_t FixedCSEnd = Offset;950 951 // Make sure the special register scavenging spill slot is closest to the952 // incoming stack pointer if a frame pointer is required and is closer953 // to the incoming rather than the final stack pointer.954 const TargetRegisterInfo *RegInfo = MF.getSubtarget().getRegisterInfo();955 bool EarlyScavengingSlots = TFI.allocateScavengingFrameIndexesNearIncomingSP(MF);956 if (RS && EarlyScavengingSlots) {957 SmallVector<int, 2> SFIs;958 RS->getScavengingFrameIndices(SFIs);959 for (int SFI : SFIs)960 AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign);961 }962 963 // FIXME: Once this is working, then enable flag will change to a target964 // check for whether the frame is large enough to want to use virtual965 // frame index registers. Functions which don't want/need this optimization966 // will continue to use the existing code path.967 if (MFI.getUseLocalStackAllocationBlock()) {968 Align Alignment = MFI.getLocalFrameMaxAlign();969 970 // Adjust to alignment boundary.971 Offset = alignTo(Offset, Alignment);972 973 LLVM_DEBUG(dbgs() << "Local frame base offset: " << Offset << "\n");974 975 // Resolve offsets for objects in the local block.976 for (unsigned i = 0, e = MFI.getLocalFrameObjectCount(); i != e; ++i) {977 std::pair<int, int64_t> Entry = MFI.getLocalFrameObjectMap(i);978 int64_t FIOffset = (StackGrowsDown ? -Offset : Offset) + Entry.second;979 LLVM_DEBUG(dbgs() << "alloc FI(" << Entry.first << ") at SP[" << FIOffset980 << "]\n");981 MFI.setObjectOffset(Entry.first, FIOffset);982 }983 // Allocate the local block984 Offset += MFI.getLocalFrameSize();985 986 MaxAlign = std::max(Alignment, MaxAlign);987 }988 989 // Retrieve the Exception Handler registration node.990 int EHRegNodeFrameIndex = std::numeric_limits<int>::max();991 if (const WinEHFuncInfo *FuncInfo = MF.getWinEHFuncInfo())992 EHRegNodeFrameIndex = FuncInfo->EHRegNodeFrameIndex;993 994 // Make sure that the stack protector comes before the local variables on the995 // stack.996 SmallSet<int, 16> ProtectedObjs;997 if (MFI.hasStackProtectorIndex()) {998 int StackProtectorFI = MFI.getStackProtectorIndex();999 StackObjSet LargeArrayObjs;1000 StackObjSet SmallArrayObjs;1001 StackObjSet AddrOfObjs;1002 1003 // If we need a stack protector, we need to make sure that1004 // LocalStackSlotPass didn't already allocate a slot for it.1005 // If we are told to use the LocalStackAllocationBlock, the stack protector1006 // is expected to be already pre-allocated.1007 if (MFI.getStackID(StackProtectorFI) != TargetStackID::Default) {1008 // If the stack protector isn't on the default stack then it's up to the1009 // target to set the stack offset.1010 assert(MFI.getObjectOffset(StackProtectorFI) != 0 &&1011 "Offset of stack protector on non-default stack expected to be "1012 "already set.");1013 assert(!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex()) &&1014 "Stack protector on non-default stack expected to not be "1015 "pre-allocated by LocalStackSlotPass.");1016 } else if (!MFI.getUseLocalStackAllocationBlock()) {1017 AdjustStackOffset(MFI, StackProtectorFI, StackGrowsDown, Offset,1018 MaxAlign);1019 } else if (!MFI.isObjectPreAllocated(MFI.getStackProtectorIndex())) {1020 llvm_unreachable(1021 "Stack protector not pre-allocated by LocalStackSlotPass.");1022 }1023 1024 // Assign large stack objects first.1025 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {1026 if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())1027 continue;1028 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)1029 continue;1030 if (RS && RS->isScavengingFrameIndex((int)i))1031 continue;1032 if (MFI.isDeadObjectIndex(i))1033 continue;1034 if (StackProtectorFI == (int)i || EHRegNodeFrameIndex == (int)i)1035 continue;1036 // Only allocate objects on the default stack.1037 if (MFI.getStackID(i) != TargetStackID::Default)1038 continue;1039 1040 switch (MFI.getObjectSSPLayout(i)) {1041 case MachineFrameInfo::SSPLK_None:1042 continue;1043 case MachineFrameInfo::SSPLK_SmallArray:1044 SmallArrayObjs.insert(i);1045 continue;1046 case MachineFrameInfo::SSPLK_AddrOf:1047 AddrOfObjs.insert(i);1048 continue;1049 case MachineFrameInfo::SSPLK_LargeArray:1050 LargeArrayObjs.insert(i);1051 continue;1052 }1053 llvm_unreachable("Unexpected SSPLayoutKind.");1054 }1055 1056 // We expect **all** the protected stack objects to be pre-allocated by1057 // LocalStackSlotPass. If it turns out that PEI still has to allocate some1058 // of them, we may end up messing up the expected order of the objects.1059 if (MFI.getUseLocalStackAllocationBlock() &&1060 !(LargeArrayObjs.empty() && SmallArrayObjs.empty() &&1061 AddrOfObjs.empty()))1062 llvm_unreachable("Found protected stack objects not pre-allocated by "1063 "LocalStackSlotPass.");1064 1065 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,1066 Offset, MaxAlign);1067 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,1068 Offset, MaxAlign);1069 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,1070 Offset, MaxAlign);1071 }1072 1073 SmallVector<int, 8> ObjectsToAllocate;1074 1075 // Then prepare to assign frame offsets to stack objects that are not used to1076 // spill callee saved registers.1077 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {1078 if (MFI.isObjectPreAllocated(i) && MFI.getUseLocalStackAllocationBlock())1079 continue;1080 if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)1081 continue;1082 if (RS && RS->isScavengingFrameIndex((int)i))1083 continue;1084 if (MFI.isDeadObjectIndex(i))1085 continue;1086 if (MFI.getStackProtectorIndex() == (int)i || EHRegNodeFrameIndex == (int)i)1087 continue;1088 if (ProtectedObjs.count(i))1089 continue;1090 // Only allocate objects on the default stack.1091 if (MFI.getStackID(i) != TargetStackID::Default)1092 continue;1093 1094 // Add the objects that we need to allocate to our working set.1095 ObjectsToAllocate.push_back(i);1096 }1097 1098 // Allocate the EH registration node first if one is present.1099 if (EHRegNodeFrameIndex != std::numeric_limits<int>::max())1100 AdjustStackOffset(MFI, EHRegNodeFrameIndex, StackGrowsDown, Offset,1101 MaxAlign);1102 1103 // Give the targets a chance to order the objects the way they like it.1104 if (MF.getTarget().getOptLevel() != CodeGenOptLevel::None &&1105 MF.getTarget().Options.StackSymbolOrdering)1106 TFI.orderFrameObjects(MF, ObjectsToAllocate);1107 1108 // Keep track of which bytes in the fixed and callee-save range are used so we1109 // can use the holes when allocating later stack objects. Only do this if1110 // stack protector isn't being used and the target requests it and we're1111 // optimizing.1112 BitVector StackBytesFree;1113 if (!ObjectsToAllocate.empty() &&1114 MF.getTarget().getOptLevel() != CodeGenOptLevel::None &&1115 MFI.getStackProtectorIndex() < 0 && TFI.enableStackSlotScavenging(MF))1116 computeFreeStackSlots(MFI, StackGrowsDown, MinCSFrameIndex, MaxCSFrameIndex,1117 FixedCSEnd, StackBytesFree);1118 1119 // Now walk the objects and actually assign base offsets to them.1120 for (auto &Object : ObjectsToAllocate)1121 if (!scavengeStackSlot(MFI, Object, StackGrowsDown, MaxAlign,1122 StackBytesFree))1123 AdjustStackOffset(MFI, Object, StackGrowsDown, Offset, MaxAlign);1124 1125 // Make sure the special register scavenging spill slot is closest to the1126 // stack pointer.1127 if (RS && !EarlyScavengingSlots) {1128 SmallVector<int, 2> SFIs;1129 RS->getScavengingFrameIndices(SFIs);1130 for (int SFI : SFIs)1131 AdjustStackOffset(MFI, SFI, StackGrowsDown, Offset, MaxAlign);1132 }1133 1134 if (!TFI.targetHandlesStackFrameRounding()) {1135 // If we have reserved argument space for call sites in the function1136 // immediately on entry to the current function, count it as part of the1137 // overall stack size.1138 if (MFI.adjustsStack() && TFI.hasReservedCallFrame(MF))1139 Offset += MFI.getMaxCallFrameSize();1140 1141 // Round up the size to a multiple of the alignment. If the function has1142 // any calls or alloca's, align to the target's StackAlignment value to1143 // ensure that the callee's frame or the alloca data is suitably aligned;1144 // otherwise, for leaf functions, align to the TransientStackAlignment1145 // value.1146 Align StackAlign;1147 if (MFI.adjustsStack() || MFI.hasVarSizedObjects() ||1148 (RegInfo->hasStackRealignment(MF) && MFI.getObjectIndexEnd() != 0))1149 StackAlign = TFI.getStackAlign();1150 else1151 StackAlign = TFI.getTransientStackAlign();1152 1153 // If the frame pointer is eliminated, all frame offsets will be relative to1154 // SP not FP. Align to MaxAlign so this works.1155 StackAlign = std::max(StackAlign, MaxAlign);1156 int64_t OffsetBeforeAlignment = Offset;1157 Offset = alignTo(Offset, StackAlign);1158 1159 // If we have increased the offset to fulfill the alignment constrants,1160 // then the scavenging spill slots may become harder to reach from the1161 // stack pointer, float them so they stay close.1162 if (StackGrowsDown && OffsetBeforeAlignment != Offset && RS &&1163 !EarlyScavengingSlots) {1164 SmallVector<int, 2> SFIs;1165 RS->getScavengingFrameIndices(SFIs);1166 LLVM_DEBUG(if (!SFIs.empty()) llvm::dbgs()1167 << "Adjusting emergency spill slots!\n";);1168 int64_t Delta = Offset - OffsetBeforeAlignment;1169 for (int SFI : SFIs) {1170 LLVM_DEBUG(llvm::dbgs()1171 << "Adjusting offset of emergency spill slot #" << SFI1172 << " from " << MFI.getObjectOffset(SFI););1173 MFI.setObjectOffset(SFI, MFI.getObjectOffset(SFI) - Delta);1174 LLVM_DEBUG(llvm::dbgs() << " to " << MFI.getObjectOffset(SFI) << "\n";);1175 }1176 }1177 }1178 1179 // Update frame info to pretend that this is part of the stack...1180 int64_t StackSize = Offset - LocalAreaOffset;1181 MFI.setStackSize(StackSize);1182 NumBytesStackSpace += StackSize;1183}1184 1185/// insertPrologEpilogCode - Scan the function for modified callee saved1186/// registers, insert spill code for these callee saved registers, then add1187/// prolog and epilog code to the function.1188void PEIImpl::insertPrologEpilogCode(MachineFunction &MF) {1189 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();1190 1191 // Add prologue to the function...1192 for (MachineBasicBlock *SaveBlock : SaveBlocks)1193 TFI.emitPrologue(MF, *SaveBlock);1194 1195 // Add epilogue to restore the callee-save registers in each exiting block.1196 for (MachineBasicBlock *RestoreBlock : RestoreBlocks)1197 TFI.emitEpilogue(MF, *RestoreBlock);1198 1199 // Zero call used registers before restoring callee-saved registers.1200 insertZeroCallUsedRegs(MF);1201 1202 for (MachineBasicBlock *SaveBlock : SaveBlocks)1203 TFI.inlineStackProbe(MF, *SaveBlock);1204 1205 // Emit additional code that is required to support segmented stacks, if1206 // we've been asked for it. This, when linked with a runtime with support1207 // for segmented stacks (libgcc is one), will result in allocating stack1208 // space in small chunks instead of one large contiguous block.1209 if (MF.shouldSplitStack()) {1210 for (MachineBasicBlock *SaveBlock : SaveBlocks)1211 TFI.adjustForSegmentedStacks(MF, *SaveBlock);1212 }1213 1214 // Emit additional code that is required to explicitly handle the stack in1215 // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The1216 // approach is rather similar to that of Segmented Stacks, but it uses a1217 // different conditional check and another BIF for allocating more stack1218 // space.1219 if (MF.getFunction().getCallingConv() == CallingConv::HiPE)1220 for (MachineBasicBlock *SaveBlock : SaveBlocks)1221 TFI.adjustForHiPEPrologue(MF, *SaveBlock);1222}1223 1224/// insertZeroCallUsedRegs - Zero out call used registers.1225void PEIImpl::insertZeroCallUsedRegs(MachineFunction &MF) {1226 const Function &F = MF.getFunction();1227 1228 if (!F.hasFnAttribute("zero-call-used-regs"))1229 return;1230 1231 using namespace ZeroCallUsedRegs;1232 1233 ZeroCallUsedRegsKind ZeroRegsKind =1234 StringSwitch<ZeroCallUsedRegsKind>(1235 F.getFnAttribute("zero-call-used-regs").getValueAsString())1236 .Case("skip", ZeroCallUsedRegsKind::Skip)1237 .Case("used-gpr-arg", ZeroCallUsedRegsKind::UsedGPRArg)1238 .Case("used-gpr", ZeroCallUsedRegsKind::UsedGPR)1239 .Case("used-arg", ZeroCallUsedRegsKind::UsedArg)1240 .Case("used", ZeroCallUsedRegsKind::Used)1241 .Case("all-gpr-arg", ZeroCallUsedRegsKind::AllGPRArg)1242 .Case("all-gpr", ZeroCallUsedRegsKind::AllGPR)1243 .Case("all-arg", ZeroCallUsedRegsKind::AllArg)1244 .Case("all", ZeroCallUsedRegsKind::All);1245 1246 if (ZeroRegsKind == ZeroCallUsedRegsKind::Skip)1247 return;1248 1249 const bool OnlyGPR = static_cast<unsigned>(ZeroRegsKind) & ONLY_GPR;1250 const bool OnlyUsed = static_cast<unsigned>(ZeroRegsKind) & ONLY_USED;1251 const bool OnlyArg = static_cast<unsigned>(ZeroRegsKind) & ONLY_ARG;1252 1253 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();1254 const BitVector AllocatableSet(TRI.getAllocatableSet(MF));1255 1256 // Mark all used registers.1257 BitVector UsedRegs(TRI.getNumRegs());1258 if (OnlyUsed)1259 for (const MachineBasicBlock &MBB : MF)1260 for (const MachineInstr &MI : MBB) {1261 // skip debug instructions1262 if (MI.isDebugInstr())1263 continue;1264 1265 for (const MachineOperand &MO : MI.operands()) {1266 if (!MO.isReg())1267 continue;1268 1269 MCRegister Reg = MO.getReg();1270 if (AllocatableSet[Reg.id()] && !MO.isImplicit() &&1271 (MO.isDef() || MO.isUse()))1272 UsedRegs.set(Reg.id());1273 }1274 }1275 1276 // Get a list of registers that are used.1277 BitVector LiveIns(TRI.getNumRegs());1278 for (const MachineBasicBlock::RegisterMaskPair &LI : MF.front().liveins())1279 LiveIns.set(LI.PhysReg);1280 1281 BitVector RegsToZero(TRI.getNumRegs());1282 for (MCRegister Reg : AllocatableSet.set_bits()) {1283 // Skip over fixed registers.1284 if (TRI.isFixedRegister(MF, Reg))1285 continue;1286 1287 // Want only general purpose registers.1288 if (OnlyGPR && !TRI.isGeneralPurposeRegister(MF, Reg))1289 continue;1290 1291 // Want only used registers.1292 if (OnlyUsed && !UsedRegs[Reg.id()])1293 continue;1294 1295 // Want only registers used for arguments.1296 if (OnlyArg) {1297 if (OnlyUsed) {1298 if (!LiveIns[Reg.id()])1299 continue;1300 } else if (!TRI.isArgumentRegister(MF, Reg)) {1301 continue;1302 }1303 }1304 1305 RegsToZero.set(Reg.id());1306 }1307 1308 // Don't clear registers that are live when leaving the function.1309 for (const MachineBasicBlock &MBB : MF)1310 for (const MachineInstr &MI : MBB.terminators()) {1311 if (!MI.isReturn())1312 continue;1313 1314 for (const auto &MO : MI.operands()) {1315 if (!MO.isReg())1316 continue;1317 1318 MCRegister Reg = MO.getReg();1319 if (!Reg)1320 continue;1321 1322 // This picks up sibling registers (e.q. %al -> %ah).1323 // FIXME: Mixing physical registers and register units is likely a bug.1324 for (MCRegUnit Unit : TRI.regunits(Reg))1325 RegsToZero.reset(static_cast<unsigned>(Unit));1326 1327 for (MCPhysReg SReg : TRI.sub_and_superregs_inclusive(Reg))1328 RegsToZero.reset(SReg);1329 }1330 }1331 1332 // Don't need to clear registers that are used/clobbered by terminating1333 // instructions.1334 for (const MachineBasicBlock &MBB : MF) {1335 if (!MBB.isReturnBlock())1336 continue;1337 1338 MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();1339 for (MachineBasicBlock::const_iterator I = MBBI, E = MBB.end(); I != E;1340 ++I) {1341 for (const MachineOperand &MO : I->operands()) {1342 if (!MO.isReg())1343 continue;1344 1345 MCRegister Reg = MO.getReg();1346 if (!Reg)1347 continue;1348 1349 for (const MCPhysReg Reg : TRI.sub_and_superregs_inclusive(Reg))1350 RegsToZero.reset(Reg);1351 }1352 }1353 }1354 1355 // Don't clear registers that must be preserved.1356 for (const MCPhysReg *CSRegs = TRI.getCalleeSavedRegs(&MF);1357 MCPhysReg CSReg = *CSRegs; ++CSRegs)1358 for (MCRegister Reg : TRI.sub_and_superregs_inclusive(CSReg))1359 RegsToZero.reset(Reg.id());1360 1361 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();1362 for (MachineBasicBlock &MBB : MF)1363 if (MBB.isReturnBlock())1364 TFI.emitZeroCallUsedRegs(RegsToZero, MBB);1365}1366 1367/// Replace all FrameIndex operands with physical register references and actual1368/// offsets.1369void PEIImpl::replaceFrameIndicesBackward(MachineFunction &MF) {1370 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();1371 1372 for (auto &MBB : MF) {1373 int SPAdj = 0;1374 if (!MBB.succ_empty()) {1375 // Get the SP adjustment for the end of MBB from the start of any of its1376 // successors. They should all be the same.1377 assert(all_of(MBB.successors(), [&MBB](const MachineBasicBlock *Succ) {1378 return Succ->getCallFrameSize() ==1379 (*MBB.succ_begin())->getCallFrameSize();1380 }));1381 const MachineBasicBlock &FirstSucc = **MBB.succ_begin();1382 SPAdj = TFI.alignSPAdjust(FirstSucc.getCallFrameSize());1383 if (TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsUp)1384 SPAdj = -SPAdj;1385 }1386 1387 replaceFrameIndicesBackward(&MBB, MF, SPAdj);1388 1389 // We can't track the call frame size after call frame pseudos have been1390 // eliminated. Set it to zero everywhere to keep MachineVerifier happy.1391 MBB.setCallFrameSize(0);1392 }1393}1394 1395/// replaceFrameIndices - Replace all MO_FrameIndex operands with physical1396/// register references and actual offsets.1397void PEIImpl::replaceFrameIndices(MachineFunction &MF) {1398 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();1399 1400 for (auto &MBB : MF) {1401 int SPAdj = TFI.alignSPAdjust(MBB.getCallFrameSize());1402 if (TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsUp)1403 SPAdj = -SPAdj;1404 1405 replaceFrameIndices(&MBB, MF, SPAdj);1406 1407 // We can't track the call frame size after call frame pseudos have been1408 // eliminated. Set it to zero everywhere to keep MachineVerifier happy.1409 MBB.setCallFrameSize(0);1410 }1411}1412 1413bool PEIImpl::replaceFrameIndexDebugInstr(MachineFunction &MF, MachineInstr &MI,1414 unsigned OpIdx, int SPAdj) {1415 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();1416 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();1417 if (MI.isDebugValue()) {1418 1419 MachineOperand &Op = MI.getOperand(OpIdx);1420 assert(MI.isDebugOperand(&Op) &&1421 "Frame indices can only appear as a debug operand in a DBG_VALUE*"1422 " machine instruction");1423 Register Reg;1424 unsigned FrameIdx = Op.getIndex();1425 unsigned Size = MF.getFrameInfo().getObjectSize(FrameIdx);1426 1427 StackOffset Offset = TFI->getFrameIndexReference(MF, FrameIdx, Reg);1428 Op.ChangeToRegister(Reg, false /*isDef*/);1429 1430 const DIExpression *DIExpr = MI.getDebugExpression();1431 1432 // If we have a direct DBG_VALUE, and its location expression isn't1433 // currently complex, then adding an offset will morph it into a1434 // complex location that is interpreted as being a memory address.1435 // This changes a pointer-valued variable to dereference that pointer,1436 // which is incorrect. Fix by adding DW_OP_stack_value.1437 1438 if (MI.isNonListDebugValue()) {1439 unsigned PrependFlags = DIExpression::ApplyOffset;1440 if (!MI.isIndirectDebugValue() && !DIExpr->isComplex())1441 PrependFlags |= DIExpression::StackValue;1442 1443 // If we have DBG_VALUE that is indirect and has a Implicit location1444 // expression need to insert a deref before prepending a Memory1445 // location expression. Also after doing this we change the DBG_VALUE1446 // to be direct.1447 if (MI.isIndirectDebugValue() && DIExpr->isImplicit()) {1448 SmallVector<uint64_t, 2> Ops = {dwarf::DW_OP_deref_size, Size};1449 bool WithStackValue = true;1450 DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);1451 // Make the DBG_VALUE direct.1452 MI.getDebugOffset().ChangeToRegister(0, false);1453 }1454 DIExpr = TRI.prependOffsetExpression(DIExpr, PrependFlags, Offset);1455 } else {1456 // The debug operand at DebugOpIndex was a frame index at offset1457 // `Offset`; now the operand has been replaced with the frame1458 // register, we must add Offset with `register x, plus Offset`.1459 unsigned DebugOpIndex = MI.getDebugOperandIndex(&Op);1460 SmallVector<uint64_t, 3> Ops;1461 TRI.getOffsetOpcodes(Offset, Ops);1462 DIExpr = DIExpression::appendOpsToArg(DIExpr, Ops, DebugOpIndex);1463 }1464 MI.getDebugExpressionOp().setMetadata(DIExpr);1465 return true;1466 }1467 1468 if (MI.isDebugPHI()) {1469 // Allow stack ref to continue onwards.1470 return true;1471 }1472 1473 // TODO: This code should be commoned with the code for1474 // PATCHPOINT. There's no good reason for the difference in1475 // implementation other than historical accident. The only1476 // remaining difference is the unconditional use of the stack1477 // pointer as the base register.1478 if (MI.getOpcode() == TargetOpcode::STATEPOINT) {1479 assert((!MI.isDebugValue() || OpIdx == 0) &&1480 "Frame indices can only appear as the first operand of a "1481 "DBG_VALUE machine instruction");1482 Register Reg;1483 MachineOperand &Offset = MI.getOperand(OpIdx + 1);1484 StackOffset refOffset = TFI->getFrameIndexReferencePreferSP(1485 MF, MI.getOperand(OpIdx).getIndex(), Reg, /*IgnoreSPUpdates*/ false);1486 assert(!refOffset.getScalable() &&1487 "Frame offsets with a scalable component are not supported");1488 Offset.setImm(Offset.getImm() + refOffset.getFixed() + SPAdj);1489 MI.getOperand(OpIdx).ChangeToRegister(Reg, false /*isDef*/);1490 return true;1491 }1492 return false;1493}1494 1495void PEIImpl::replaceFrameIndicesBackward(MachineBasicBlock *BB,1496 MachineFunction &MF, int &SPAdj) {1497 assert(MF.getSubtarget().getRegisterInfo() &&1498 "getRegisterInfo() must be implemented!");1499 1500 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();1501 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();1502 const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();1503 1504 RegScavenger *LocalRS = FrameIndexEliminationScavenging ? RS : nullptr;1505 if (LocalRS)1506 LocalRS->enterBasicBlockEnd(*BB);1507 1508 for (MachineBasicBlock::iterator I = BB->end(); I != BB->begin();) {1509 MachineInstr &MI = *std::prev(I);1510 1511 if (TII.isFrameInstr(MI)) {1512 SPAdj -= TII.getSPAdjust(MI);1513 TFI.eliminateCallFramePseudoInstr(MF, *BB, &MI);1514 continue;1515 }1516 1517 // Step backwards to get the liveness state at (immedately after) MI.1518 if (LocalRS)1519 LocalRS->backward(I);1520 1521 bool RemovedMI = false;1522 for (const auto &[Idx, Op] : enumerate(MI.operands())) {1523 if (!Op.isFI())1524 continue;1525 1526 if (replaceFrameIndexDebugInstr(MF, MI, Idx, SPAdj))1527 continue;1528 1529 // Eliminate this FrameIndex operand.1530 RemovedMI = TRI.eliminateFrameIndex(MI, SPAdj, Idx, LocalRS);1531 if (RemovedMI)1532 break;1533 }1534 1535 if (!RemovedMI)1536 --I;1537 }1538}1539 1540void PEIImpl::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,1541 int &SPAdj) {1542 assert(MF.getSubtarget().getRegisterInfo() &&1543 "getRegisterInfo() must be implemented!");1544 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();1545 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();1546 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();1547 1548 bool InsideCallSequence = false;1549 1550 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {1551 if (TII.isFrameInstr(*I)) {1552 InsideCallSequence = TII.isFrameSetup(*I);1553 SPAdj += TII.getSPAdjust(*I);1554 I = TFI->eliminateCallFramePseudoInstr(MF, *BB, I);1555 continue;1556 }1557 1558 MachineInstr &MI = *I;1559 bool DoIncr = true;1560 bool DidFinishLoop = true;1561 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {1562 if (!MI.getOperand(i).isFI())1563 continue;1564 1565 if (replaceFrameIndexDebugInstr(MF, MI, i, SPAdj))1566 continue;1567 1568 // Some instructions (e.g. inline asm instructions) can have1569 // multiple frame indices and/or cause eliminateFrameIndex1570 // to insert more than one instruction. We need the register1571 // scavenger to go through all of these instructions so that1572 // it can update its register information. We keep the1573 // iterator at the point before insertion so that we can1574 // revisit them in full.1575 bool AtBeginning = (I == BB->begin());1576 if (!AtBeginning) --I;1577 1578 // If this instruction has a FrameIndex operand, we need to1579 // use that target machine register info object to eliminate1580 // it.1581 TRI.eliminateFrameIndex(MI, SPAdj, i, RS);1582 1583 // Reset the iterator if we were at the beginning of the BB.1584 if (AtBeginning) {1585 I = BB->begin();1586 DoIncr = false;1587 }1588 1589 DidFinishLoop = false;1590 break;1591 }1592 1593 // If we are looking at a call sequence, we need to keep track of1594 // the SP adjustment made by each instruction in the sequence.1595 // This includes both the frame setup/destroy pseudos (handled above),1596 // as well as other instructions that have side effects w.r.t the SP.1597 // Note that this must come after eliminateFrameIndex, because1598 // if I itself referred to a frame index, we shouldn't count its own1599 // adjustment.1600 if (DidFinishLoop && InsideCallSequence)1601 SPAdj += TII.getSPAdjust(MI);1602 1603 if (DoIncr && I != BB->end())1604 ++I;1605 }1606}1607