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