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