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