lib/CodeGen/PrologEpilogInserter.cpp

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