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