6b23b52ec5f0f57d0a0604b59248e29adffd822f
[oota-llvm.git] / 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 MCPhysReg *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     StackObjSet SmallArrayObjs;
557     StackObjSet AddrOfObjs;
558
559     AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), StackGrowsDown,
560                       Offset, MaxAlign);
561
562     // Assign large stack objects first.
563     for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
564       if (MFI->isObjectPreAllocated(i) &&
565           MFI->getUseLocalStackAllocationBlock())
566         continue;
567       if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
568         continue;
569       if (RS && RS->isScavengingFrameIndex((int)i))
570         continue;
571       if (MFI->isDeadObjectIndex(i))
572         continue;
573       if (MFI->getStackProtectorIndex() == (int)i)
574         continue;
575
576       switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) {
577       case StackProtector::SSPLK_None:
578         continue;
579       case StackProtector::SSPLK_SmallArray:
580         SmallArrayObjs.insert(i);
581         continue;
582       case StackProtector::SSPLK_AddrOf:
583         AddrOfObjs.insert(i);
584         continue;
585       case StackProtector::SSPLK_LargeArray:
586         LargeArrayObjs.insert(i);
587         continue;
588       }
589       llvm_unreachable("Unexpected SSPLayoutKind.");
590     }
591
592     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
593                           Offset, MaxAlign);
594     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
595                           Offset, MaxAlign);
596     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
597                           Offset, MaxAlign);
598   }
599
600   // Then assign frame offsets to stack objects that are not used to spill
601   // callee saved registers.
602   for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
603     if (MFI->isObjectPreAllocated(i) &&
604         MFI->getUseLocalStackAllocationBlock())
605       continue;
606     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
607       continue;
608     if (RS && RS->isScavengingFrameIndex((int)i))
609       continue;
610     if (MFI->isDeadObjectIndex(i))
611       continue;
612     if (MFI->getStackProtectorIndex() == (int)i)
613       continue;
614     if (ProtectedObjs.count(i))
615       continue;
616
617     AdjustStackOffset(MFI, i, StackGrowsDown, Offset, MaxAlign);
618   }
619
620   // Make sure the special register scavenging spill slot is closest to the
621   // stack pointer.
622   if (RS && !EarlyScavengingSlots) {
623     SmallVector<int, 2> SFIs;
624     RS->getScavengingFrameIndices(SFIs);
625     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
626            IE = SFIs.end(); I != IE; ++I)
627       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign);
628   }
629
630   if (!TFI.targetHandlesStackFrameRounding()) {
631     // If we have reserved argument space for call sites in the function
632     // immediately on entry to the current function, count it as part of the
633     // overall stack size.
634     if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn))
635       Offset += MFI->getMaxCallFrameSize();
636
637     // Round up the size to a multiple of the alignment.  If the function has
638     // any calls or alloca's, align to the target's StackAlignment value to
639     // ensure that the callee's frame or the alloca data is suitably aligned;
640     // otherwise, for leaf functions, align to the TransientStackAlignment
641     // value.
642     unsigned StackAlign;
643     if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
644         (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
645       StackAlign = TFI.getStackAlignment();
646     else
647       StackAlign = TFI.getTransientStackAlignment();
648
649     // If the frame pointer is eliminated, all frame offsets will be relative to
650     // SP not FP. Align to MaxAlign so this works.
651     StackAlign = std::max(StackAlign, MaxAlign);
652     unsigned AlignMask = StackAlign - 1;
653     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
654   }
655
656   // Update frame info to pretend that this is part of the stack...
657   int64_t StackSize = Offset - LocalAreaOffset;
658   MFI->setStackSize(StackSize);
659   NumBytesStackSpace += StackSize;
660 }
661
662 /// insertPrologEpilogCode - Scan the function for modified callee saved
663 /// registers, insert spill code for these callee saved registers, then add
664 /// prolog and epilog code to the function.
665 ///
666 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
667   const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
668
669   // Add prologue to the function...
670   TFI.emitPrologue(Fn);
671
672   // Add epilogue to restore the callee-save registers in each exiting block
673   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
674     // If last instruction is a return instruction, add an epilogue
675     if (!I->empty() && I->back().isReturn())
676       TFI.emitEpilogue(Fn, *I);
677   }
678
679   // Emit additional code that is required to support segmented stacks, if
680   // we've been asked for it.  This, when linked with a runtime with support
681   // for segmented stacks (libgcc is one), will result in allocating stack
682   // space in small chunks instead of one large contiguous block.
683   if (Fn.shouldSplitStack())
684     TFI.adjustForSegmentedStacks(Fn);
685
686   // Emit additional code that is required to explicitly handle the stack in
687   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
688   // approach is rather similar to that of Segmented Stacks, but it uses a
689   // different conditional check and another BIF for allocating more stack
690   // space.
691   if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE)
692     TFI.adjustForHiPEPrologue(Fn);
693 }
694
695 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
696 /// register references and actual offsets.
697 ///
698 void PEI::replaceFrameIndices(MachineFunction &Fn) {
699   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
700
701   // Store SPAdj at exit of a basic block.
702   SmallVector<int, 8> SPState;
703   SPState.resize(Fn.getNumBlockIDs());
704   SmallPtrSet<MachineBasicBlock*, 8> Reachable;
705
706   // Iterate over the reachable blocks in DFS order.
707   for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> >
708        DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
709        DFI != DFE; ++DFI) {
710     int SPAdj = 0;
711     // Check the exit state of the DFS stack predecessor.
712     if (DFI.getPathLength() >= 2) {
713       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
714       assert(Reachable.count(StackPred) &&
715              "DFS stack predecessor is already visited.\n");
716       SPAdj = SPState[StackPred->getNumber()];
717     }
718     MachineBasicBlock *BB = *DFI;
719     replaceFrameIndices(BB, Fn, SPAdj);
720     SPState[BB->getNumber()] = SPAdj;
721   }
722
723   // Handle the unreachable blocks.
724   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
725     if (Reachable.count(BB))
726       // Already handled in DFS traversal.
727       continue;
728     int SPAdj = 0;
729     replaceFrameIndices(BB, Fn, SPAdj);
730   }
731 }
732
733 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
734                               int &SPAdj) {
735   const TargetMachine &TM = Fn.getTarget();
736   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
737   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
738   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
739   const TargetFrameLowering *TFI = TM.getFrameLowering();
740   bool StackGrowsDown =
741     TFI->getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
742   int FrameSetupOpcode   = TII.getCallFrameSetupOpcode();
743   int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
744
745   if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
746
747   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
748
749     if (I->getOpcode() == FrameSetupOpcode ||
750         I->getOpcode() == FrameDestroyOpcode) {
751       // Remember how much SP has been adjusted to create the call
752       // frame.
753       int Size = I->getOperand(0).getImm();
754
755       if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
756           (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
757         Size = -Size;
758
759       SPAdj += Size;
760
761       MachineBasicBlock::iterator PrevI = BB->end();
762       if (I != BB->begin()) PrevI = std::prev(I);
763       TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
764
765       // Visit the instructions created by eliminateCallFramePseudoInstr().
766       if (PrevI == BB->end())
767         I = BB->begin();     // The replaced instr was the first in the block.
768       else
769         I = std::next(PrevI);
770       continue;
771     }
772
773     MachineInstr *MI = I;
774     bool DoIncr = true;
775     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
776       if (!MI->getOperand(i).isFI())
777         continue;
778
779       // Frame indicies in debug values are encoded in a target independent
780       // way with simply the frame index and offset rather than any
781       // target-specific addressing mode.
782       if (MI->isDebugValue()) {
783         assert(i == 0 && "Frame indicies can only appear as the first "
784                          "operand of a DBG_VALUE machine instruction");
785         unsigned Reg;
786         MachineOperand &Offset = MI->getOperand(1);
787         Offset.setImm(Offset.getImm() +
788                       TFI->getFrameIndexReference(
789                           Fn, MI->getOperand(0).getIndex(), Reg));
790         MI->getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
791         continue;
792       }
793
794       // Some instructions (e.g. inline asm instructions) can have
795       // multiple frame indices and/or cause eliminateFrameIndex
796       // to insert more than one instruction. We need the register
797       // scavenger to go through all of these instructions so that
798       // it can update its register information. We keep the
799       // iterator at the point before insertion so that we can
800       // revisit them in full.
801       bool AtBeginning = (I == BB->begin());
802       if (!AtBeginning) --I;
803
804       // If this instruction has a FrameIndex operand, we need to
805       // use that target machine register info object to eliminate
806       // it.
807       TRI.eliminateFrameIndex(MI, SPAdj, i,
808                               FrameIndexVirtualScavenging ?  NULL : RS);
809
810       // Reset the iterator if we were at the beginning of the BB.
811       if (AtBeginning) {
812         I = BB->begin();
813         DoIncr = false;
814       }
815
816       MI = 0;
817       break;
818     }
819
820     if (DoIncr && I != BB->end()) ++I;
821
822     // Update register states.
823     if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
824   }
825 }
826
827 /// scavengeFrameVirtualRegs - Replace all frame index virtual registers
828 /// with physical registers. Use the register scavenger to find an
829 /// appropriate register to use.
830 ///
831 /// FIXME: Iterating over the instruction stream is unnecessary. We can simply
832 /// iterate over the vreg use list, which at this point only contains machine
833 /// operands for which eliminateFrameIndex need a new scratch reg.
834 void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
835   // Run through the instructions and find any virtual registers.
836   for (MachineFunction::iterator BB = Fn.begin(),
837        E = Fn.end(); BB != E; ++BB) {
838     RS->enterBasicBlock(BB);
839
840     int SPAdj = 0;
841
842     // The instruction stream may change in the loop, so check BB->end()
843     // directly.
844     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
845       // We might end up here again with a NULL iterator if we scavenged a
846       // register for which we inserted spill code for definition by what was
847       // originally the first instruction in BB.
848       if (I == MachineBasicBlock::iterator(NULL))
849         I = BB->begin();
850
851       MachineInstr *MI = I;
852       MachineBasicBlock::iterator J = std::next(I);
853       MachineBasicBlock::iterator P =
854           I == BB->begin() ? MachineBasicBlock::iterator(NULL) : std::prev(I);
855
856       // RS should process this instruction before we might scavenge at this
857       // location. This is because we might be replacing a virtual register
858       // defined by this instruction, and if so, registers killed by this
859       // instruction are available, and defined registers are not.
860       RS->forward(I);
861
862       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
863         if (MI->getOperand(i).isReg()) {
864           MachineOperand &MO = MI->getOperand(i);
865           unsigned Reg = MO.getReg();
866           if (Reg == 0)
867             continue;
868           if (!TargetRegisterInfo::isVirtualRegister(Reg))
869             continue;
870
871           // When we first encounter a new virtual register, it
872           // must be a definition.
873           assert(MI->getOperand(i).isDef() &&
874                  "frame index virtual missing def!");
875           // Scavenge a new scratch register
876           const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
877           unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
878
879           ++NumScavengedRegs;
880
881           // Replace this reference to the virtual register with the
882           // scratch register.
883           assert (ScratchReg && "Missing scratch register!");
884           Fn.getRegInfo().replaceRegWith(Reg, ScratchReg);
885
886           // Because this instruction was processed by the RS before this
887           // register was allocated, make sure that the RS now records the
888           // register as being used.
889           RS->setUsed(ScratchReg);
890         }
891       }
892
893       // If the scavenger needed to use one of its spill slots, the
894       // spill code will have been inserted in between I and J. This is a
895       // problem because we need the spill code before I: Move I to just
896       // prior to J.
897       if (I != std::prev(J)) {
898         BB->splice(J, BB, I);
899
900         // Before we move I, we need to prepare the RS to visit I again.
901         // Specifically, RS will assert if it sees uses of registers that
902         // it believes are undefined. Because we have already processed
903         // register kills in I, when it visits I again, it will believe that
904         // those registers are undefined. To avoid this situation, unprocess
905         // the instruction I.
906         assert(RS->getCurrentPosition() == I &&
907           "The register scavenger has an unexpected position");
908         I = P;
909         RS->unprocess(P);
910       } else
911         ++I;
912     }
913   }
914 }