Start of revamping the register scavenging in PEI. ARM Thumb1 is the driving
[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 // This pass provides an optional shrink wrapping variant of prolog/epilog
18 // insertion, enabled via --shrink-wrap. See ShrinkWrapping.cpp.
19 //
20 //===----------------------------------------------------------------------===//
21
22 #include "PrologEpilogInserter.h"
23 #include "llvm/CodeGen/MachineDominators.h"
24 #include "llvm/CodeGen/MachineLoopInfo.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineFrameInfo.h"
27 #include "llvm/CodeGen/MachineModuleInfo.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 #include "llvm/CodeGen/RegisterScavenging.h"
30 #include "llvm/Target/TargetMachine.h"
31 #include "llvm/Target/TargetRegisterInfo.h"
32 #include "llvm/Target/TargetFrameInfo.h"
33 #include "llvm/Target/TargetInstrInfo.h"
34 #include "llvm/Support/CommandLine.h"
35 #include "llvm/Support/Compiler.h"
36 #include "llvm/ADT/IndexedMap.h"
37 #include "llvm/ADT/STLExtras.h"
38 #include <climits>
39
40 using namespace llvm;
41
42 char PEI::ID = 0;
43
44 static RegisterPass<PEI>
45 X("prologepilog", "Prologue/Epilogue Insertion");
46
47 // FIXME: For now, the frame index scavenging is off by default and only
48 // used by the Thumb1 target. When it's the default and replaces the current
49 // on-the-fly PEI scavenging for all targets, requiresRegisterScavenging()
50 // will replace this.
51 cl::opt<bool>
52 FrameIndexVirtualScavenging("enable-frame-index-scavenging",
53                             cl::Hidden,
54                             cl::desc("Enable frame index elimination with"
55                                      "virtual register scavenging"));
56
57 /// createPrologEpilogCodeInserter - This function returns a pass that inserts
58 /// prolog and epilog code, and eliminates abstract frame references.
59 ///
60 FunctionPass *llvm::createPrologEpilogCodeInserter() { return new PEI(); }
61
62 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
63 /// frame indexes with appropriate references.
64 ///
65 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
66   const Function* F = Fn.getFunction();
67   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
68   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
69
70   // Get MachineModuleInfo so that we can track the construction of the
71   // frame.
72   if (MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>())
73     Fn.getFrameInfo()->setMachineModuleInfo(MMI);
74
75   // Calculate the MaxCallFrameSize and HasCalls variables for the function's
76   // frame information. Also eliminates call frame pseudo instructions.
77   calculateCallsInformation(Fn);
78
79   // Allow the target machine to make some adjustments to the function
80   // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
81   TRI->processFunctionBeforeCalleeSavedScan(Fn, RS);
82
83   // Scan the function for modified callee saved registers and insert spill code
84   // for any callee saved registers that are modified.
85   calculateCalleeSavedRegisters(Fn);
86
87   // Determine placement of CSR spill/restore code:
88   //  - with shrink wrapping, place spills and restores to tightly
89   //    enclose regions in the Machine CFG of the function where
90   //    they are used. Without shrink wrapping
91   //  - default (no shrink wrapping), place all spills in the
92   //    entry block, all restores in return blocks.
93   placeCSRSpillsAndRestores(Fn);
94
95   // Add the code to save and restore the callee saved registers
96   if (!F->hasFnAttr(Attribute::Naked))
97     insertCSRSpillsAndRestores(Fn);
98
99   // Allow the target machine to make final modifications to the function
100   // before the frame layout is finalized.
101   TRI->processFunctionBeforeFrameFinalized(Fn);
102
103   // Calculate actual frame offsets for all abstract stack objects...
104   calculateFrameObjectOffsets(Fn);
105
106   // Add prolog and epilog code to the function.  This function is required
107   // to align the stack frame as necessary for any stack variables or
108   // called functions.  Because of this, calculateCalleeSavedRegisters
109   // must be called before this function in order to set the HasCalls
110   // and MaxCallFrameSize variables.
111   if (!F->hasFnAttr(Attribute::Naked))
112     insertPrologEpilogCode(Fn);
113
114   // Replace all MO_FrameIndex operands with physical register references
115   // and actual offsets.
116   //
117   replaceFrameIndices(Fn);
118
119   // If register scavenging is needed, as we've enabled doing it as a
120   // post-pass, scavenge the virtual registers that frame index elimiation
121   // inserted.
122   if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
123     scavengeFrameVirtualRegs(Fn);
124
125   delete RS;
126   clearAllSets();
127   return true;
128 }
129
130 #if 0
131 void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
132   AU.setPreservesCFG();
133   if (ShrinkWrapping || ShrinkWrapFunc != "") {
134     AU.addRequired<MachineLoopInfo>();
135     AU.addRequired<MachineDominatorTree>();
136   }
137   AU.addPreserved<MachineLoopInfo>();
138   AU.addPreserved<MachineDominatorTree>();
139   MachineFunctionPass::getAnalysisUsage(AU);
140 }
141 #endif
142
143 /// calculateCallsInformation - Calculate the MaxCallFrameSize and HasCalls
144 /// variables for the function's frame information and eliminate call frame
145 /// pseudo instructions.
146 void PEI::calculateCallsInformation(MachineFunction &Fn) {
147   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
148
149   unsigned MaxCallFrameSize = 0;
150   bool HasCalls = false;
151
152   // Get the function call frame set-up and tear-down instruction opcode
153   int FrameSetupOpcode   = RegInfo->getCallFrameSetupOpcode();
154   int FrameDestroyOpcode = RegInfo->getCallFrameDestroyOpcode();
155
156   // Early exit for targets which have no call frame setup/destroy pseudo
157   // instructions.
158   if (FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
159     return;
160
161   std::vector<MachineBasicBlock::iterator> FrameSDOps;
162   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
163     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
164       if (I->getOpcode() == FrameSetupOpcode ||
165           I->getOpcode() == FrameDestroyOpcode) {
166         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
167                " instructions should have a single immediate argument!");
168         unsigned Size = I->getOperand(0).getImm();
169         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
170         HasCalls = true;
171         FrameSDOps.push_back(I);
172       } else if (I->getOpcode() == TargetInstrInfo::INLINEASM) {
173         // An InlineAsm might be a call; assume it is to get the stack frame
174         // aligned correctly for calls.
175         HasCalls = true;
176       }
177
178   MachineFrameInfo *FFI = Fn.getFrameInfo();
179   FFI->setHasCalls(HasCalls);
180   FFI->setMaxCallFrameSize(MaxCallFrameSize);
181
182   for (std::vector<MachineBasicBlock::iterator>::iterator
183          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
184     MachineBasicBlock::iterator I = *i;
185
186     // If call frames are not being included as part of the stack frame, and
187     // there is no dynamic allocation (therefore referencing frame slots off
188     // sp), leave the pseudo ops alone. We'll eliminate them later.
189     if (RegInfo->hasReservedCallFrame(Fn) || RegInfo->hasFP(Fn))
190       RegInfo->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
191   }
192 }
193
194
195 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
196 /// registers.
197 void PEI::calculateCalleeSavedRegisters(MachineFunction &Fn) {
198   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
199   const TargetFrameInfo *TFI = Fn.getTarget().getFrameInfo();
200   MachineFrameInfo *FFI = Fn.getFrameInfo();
201
202   // Get the callee saved register list...
203   const unsigned *CSRegs = RegInfo->getCalleeSavedRegs(&Fn);
204
205   // These are used to keep track the callee-save area. Initialize them.
206   MinCSFrameIndex = INT_MAX;
207   MaxCSFrameIndex = 0;
208
209   // Early exit for targets which have no callee saved registers.
210   if (CSRegs == 0 || CSRegs[0] == 0)
211     return;
212
213   // Figure out which *callee saved* registers are modified by the current
214   // function, thus needing to be saved and restored in the prolog/epilog.
215   const TargetRegisterClass * const *CSRegClasses =
216     RegInfo->getCalleeSavedRegClasses(&Fn);
217
218   std::vector<CalleeSavedInfo> CSI;
219   for (unsigned i = 0; CSRegs[i]; ++i) {
220     unsigned Reg = CSRegs[i];
221     if (Fn.getRegInfo().isPhysRegUsed(Reg)) {
222       // If the reg is modified, save it!
223       CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
224     } else {
225       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
226            *AliasSet; ++AliasSet) {  // Check alias registers too.
227         if (Fn.getRegInfo().isPhysRegUsed(*AliasSet)) {
228           CSI.push_back(CalleeSavedInfo(Reg, CSRegClasses[i]));
229           break;
230         }
231       }
232     }
233   }
234
235   if (CSI.empty())
236     return;   // Early exit if no callee saved registers are modified!
237
238   unsigned NumFixedSpillSlots;
239   const std::pair<unsigned,int> *FixedSpillSlots =
240     TFI->getCalleeSavedSpillSlots(NumFixedSpillSlots);
241
242   // Now that we know which registers need to be saved and restored, allocate
243   // stack slots for them.
244   for (std::vector<CalleeSavedInfo>::iterator
245          I = CSI.begin(), E = CSI.end(); I != E; ++I) {
246     unsigned Reg = I->getReg();
247     const TargetRegisterClass *RC = I->getRegClass();
248
249     int FrameIdx;
250     if (RegInfo->hasReservedSpillSlot(Fn, Reg, FrameIdx)) {
251       I->setFrameIdx(FrameIdx);
252       continue;
253     }
254
255     // Check to see if this physreg must be spilled to a particular stack slot
256     // on this target.
257     const std::pair<unsigned,int> *FixedSlot = FixedSpillSlots;
258     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
259            FixedSlot->first != Reg)
260       ++FixedSlot;
261
262     if (FixedSlot == FixedSpillSlots + NumFixedSpillSlots) {
263       // Nope, just spill it anywhere convenient.
264       unsigned Align = RC->getAlignment();
265       unsigned StackAlign = TFI->getStackAlignment();
266
267       // We may not be able to satisfy the desired alignment specification of
268       // the TargetRegisterClass if the stack alignment is smaller. Use the
269       // min.
270       Align = std::min(Align, StackAlign);
271       FrameIdx = FFI->CreateStackObject(RC->getSize(), Align);
272       if ((unsigned)FrameIdx < MinCSFrameIndex) MinCSFrameIndex = FrameIdx;
273       if ((unsigned)FrameIdx > MaxCSFrameIndex) MaxCSFrameIndex = FrameIdx;
274     } else {
275       // Spill it to the stack where we must.
276       FrameIdx = FFI->CreateFixedObject(RC->getSize(), FixedSlot->second);
277     }
278
279     I->setFrameIdx(FrameIdx);
280   }
281
282   FFI->setCalleeSavedInfo(CSI);
283 }
284
285 /// insertCSRSpillsAndRestores - Insert spill and restore code for
286 /// callee saved registers used in the function, handling shrink wrapping.
287 ///
288 void PEI::insertCSRSpillsAndRestores(MachineFunction &Fn) {
289   // Get callee saved register information.
290   MachineFrameInfo *FFI = Fn.getFrameInfo();
291   const std::vector<CalleeSavedInfo> &CSI = FFI->getCalleeSavedInfo();
292
293   FFI->setCalleeSavedInfoValid(true);
294
295   // Early exit if no callee saved registers are modified!
296   if (CSI.empty())
297     return;
298
299   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
300   MachineBasicBlock::iterator I;
301
302   if (! ShrinkWrapThisFunction) {
303     // Spill using target interface.
304     I = EntryBlock->begin();
305     if (!TII.spillCalleeSavedRegisters(*EntryBlock, I, CSI)) {
306       for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
307         // Add the callee-saved register as live-in.
308         // It's killed at the spill.
309         EntryBlock->addLiveIn(CSI[i].getReg());
310
311         // Insert the spill to the stack frame.
312         TII.storeRegToStackSlot(*EntryBlock, I, CSI[i].getReg(), true,
313                                 CSI[i].getFrameIdx(), CSI[i].getRegClass());
314       }
315     }
316
317     // Restore using target interface.
318     for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) {
319       MachineBasicBlock* MBB = ReturnBlocks[ri];
320       I = MBB->end(); --I;
321
322       // Skip over all terminator instructions, which are part of the return
323       // sequence.
324       MachineBasicBlock::iterator I2 = I;
325       while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
326         I = I2;
327
328       bool AtStart = I == MBB->begin();
329       MachineBasicBlock::iterator BeforeI = I;
330       if (!AtStart)
331         --BeforeI;
332
333       // Restore all registers immediately before the return and any
334       // terminators that preceed it.
335       if (!TII.restoreCalleeSavedRegisters(*MBB, I, CSI)) {
336         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
337           TII.loadRegFromStackSlot(*MBB, I, CSI[i].getReg(),
338                                    CSI[i].getFrameIdx(),
339                                    CSI[i].getRegClass());
340           assert(I != MBB->begin() &&
341                  "loadRegFromStackSlot didn't insert any code!");
342           // Insert in reverse order.  loadRegFromStackSlot can insert
343           // multiple instructions.
344           if (AtStart)
345             I = MBB->begin();
346           else {
347             I = BeforeI;
348             ++I;
349           }
350         }
351       }
352     }
353     return;
354   }
355
356   // Insert spills.
357   std::vector<CalleeSavedInfo> blockCSI;
358   for (CSRegBlockMap::iterator BI = CSRSave.begin(),
359          BE = CSRSave.end(); BI != BE; ++BI) {
360     MachineBasicBlock* MBB = BI->first;
361     CSRegSet save = BI->second;
362
363     if (save.empty())
364       continue;
365
366     blockCSI.clear();
367     for (CSRegSet::iterator RI = save.begin(),
368            RE = save.end(); RI != RE; ++RI) {
369       blockCSI.push_back(CSI[*RI]);
370     }
371     assert(blockCSI.size() > 0 &&
372            "Could not collect callee saved register info");
373
374     I = MBB->begin();
375
376     // When shrink wrapping, use stack slot stores/loads.
377     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
378       // Add the callee-saved register as live-in.
379       // It's killed at the spill.
380       MBB->addLiveIn(blockCSI[i].getReg());
381
382       // Insert the spill to the stack frame.
383       TII.storeRegToStackSlot(*MBB, I, blockCSI[i].getReg(),
384                               true,
385                               blockCSI[i].getFrameIdx(),
386                               blockCSI[i].getRegClass());
387     }
388   }
389
390   for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
391          BE = CSRRestore.end(); BI != BE; ++BI) {
392     MachineBasicBlock* MBB = BI->first;
393     CSRegSet restore = BI->second;
394
395     if (restore.empty())
396       continue;
397
398     blockCSI.clear();
399     for (CSRegSet::iterator RI = restore.begin(),
400            RE = restore.end(); RI != RE; ++RI) {
401       blockCSI.push_back(CSI[*RI]);
402     }
403     assert(blockCSI.size() > 0 &&
404            "Could not find callee saved register info");
405
406     // If MBB is empty and needs restores, insert at the _beginning_.
407     if (MBB->empty()) {
408       I = MBB->begin();
409     } else {
410       I = MBB->end();
411       --I;
412
413       // Skip over all terminator instructions, which are part of the
414       // return sequence.
415       if (! I->getDesc().isTerminator()) {
416         ++I;
417       } else {
418         MachineBasicBlock::iterator I2 = I;
419         while (I2 != MBB->begin() && (--I2)->getDesc().isTerminator())
420           I = I2;
421       }
422     }
423
424     bool AtStart = I == MBB->begin();
425     MachineBasicBlock::iterator BeforeI = I;
426     if (!AtStart)
427       --BeforeI;
428
429     // Restore all registers immediately before the return and any
430     // terminators that preceed it.
431     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
432       TII.loadRegFromStackSlot(*MBB, I, blockCSI[i].getReg(),
433                                blockCSI[i].getFrameIdx(),
434                                blockCSI[i].getRegClass());
435       assert(I != MBB->begin() &&
436              "loadRegFromStackSlot didn't insert any code!");
437       // Insert in reverse order.  loadRegFromStackSlot can insert
438       // multiple instructions.
439       if (AtStart)
440         I = MBB->begin();
441       else {
442         I = BeforeI;
443         ++I;
444       }
445     }
446   }
447 }
448
449 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
450 static inline void
451 AdjustStackOffset(MachineFrameInfo *FFI, int FrameIdx,
452                   bool StackGrowsDown, int64_t &Offset,
453                   unsigned &MaxAlign) {
454   // If the stack grows down, add the object size to find the lowest address.
455   if (StackGrowsDown)
456     Offset += FFI->getObjectSize(FrameIdx);
457
458   unsigned Align = FFI->getObjectAlignment(FrameIdx);
459
460   // If the alignment of this object is greater than that of the stack, then
461   // increase the stack alignment to match.
462   MaxAlign = std::max(MaxAlign, Align);
463
464   // Adjust to alignment boundary.
465   Offset = (Offset + Align - 1) / Align * Align;
466
467   if (StackGrowsDown) {
468     FFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
469   } else {
470     FFI->setObjectOffset(FrameIdx, Offset);
471     Offset += FFI->getObjectSize(FrameIdx);
472   }
473 }
474
475 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
476 /// abstract stack objects.
477 ///
478 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
479   const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
480
481   bool StackGrowsDown =
482     TFI.getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
483
484   // Loop over all of the stack objects, assigning sequential addresses...
485   MachineFrameInfo *FFI = Fn.getFrameInfo();
486
487   unsigned MaxAlign = FFI->getMaxAlignment();
488
489   // Start at the beginning of the local area.
490   // The Offset is the distance from the stack top in the direction
491   // of stack growth -- so it's always nonnegative.
492   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
493   if (StackGrowsDown)
494     LocalAreaOffset = -LocalAreaOffset;
495   assert(LocalAreaOffset >= 0
496          && "Local area offset should be in direction of stack growth");
497   int64_t Offset = LocalAreaOffset;
498
499   // If there are fixed sized objects that are preallocated in the local area,
500   // non-fixed objects can't be allocated right at the start of local area.
501   // We currently don't support filling in holes in between fixed sized
502   // objects, so we adjust 'Offset' to point to the end of last fixed sized
503   // preallocated object.
504   for (int i = FFI->getObjectIndexBegin(); i != 0; ++i) {
505     int64_t FixedOff;
506     if (StackGrowsDown) {
507       // The maximum distance from the stack pointer is at lower address of
508       // the object -- which is given by offset. For down growing stack
509       // the offset is negative, so we negate the offset to get the distance.
510       FixedOff = -FFI->getObjectOffset(i);
511     } else {
512       // The maximum distance from the start pointer is at the upper
513       // address of the object.
514       FixedOff = FFI->getObjectOffset(i) + FFI->getObjectSize(i);
515     }
516     if (FixedOff > Offset) Offset = FixedOff;
517   }
518
519   // First assign frame offsets to stack objects that are used to spill
520   // callee saved registers.
521   if (StackGrowsDown) {
522     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
523       // If stack grows down, we need to add size of find the lowest
524       // address of the object.
525       Offset += FFI->getObjectSize(i);
526
527       unsigned Align = FFI->getObjectAlignment(i);
528       // If the alignment of this object is greater than that of the stack,
529       // then increase the stack alignment to match.
530       MaxAlign = std::max(MaxAlign, Align);
531       // Adjust to alignment boundary
532       Offset = (Offset+Align-1)/Align*Align;
533
534       FFI->setObjectOffset(i, -Offset);        // Set the computed offset
535     }
536   } else {
537     int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex;
538     for (int i = MaxCSFI; i >= MinCSFI ; --i) {
539       unsigned Align = FFI->getObjectAlignment(i);
540       // If the alignment of this object is greater than that of the stack,
541       // then increase the stack alignment to match.
542       MaxAlign = std::max(MaxAlign, Align);
543       // Adjust to alignment boundary
544       Offset = (Offset+Align-1)/Align*Align;
545
546       FFI->setObjectOffset(i, Offset);
547       Offset += FFI->getObjectSize(i);
548     }
549   }
550
551   // Make sure the special register scavenging spill slot is closest to the
552   // frame pointer if a frame pointer is required.
553   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
554   if (RS && RegInfo->hasFP(Fn)) {
555     int SFI = RS->getScavengingFrameIndex();
556     if (SFI >= 0)
557       AdjustStackOffset(FFI, SFI, StackGrowsDown, Offset, MaxAlign);
558   }
559
560   // Make sure that the stack protector comes before the local variables on the
561   // stack.
562   if (FFI->getStackProtectorIndex() >= 0)
563     AdjustStackOffset(FFI, FFI->getStackProtectorIndex(), StackGrowsDown,
564                       Offset, MaxAlign);
565
566   // Then assign frame offsets to stack objects that are not used to spill
567   // callee saved registers.
568   for (unsigned i = 0, e = FFI->getObjectIndexEnd(); i != e; ++i) {
569     if (i >= MinCSFrameIndex && i <= MaxCSFrameIndex)
570       continue;
571     if (RS && (int)i == RS->getScavengingFrameIndex())
572       continue;
573     if (FFI->isDeadObjectIndex(i))
574       continue;
575     if (FFI->getStackProtectorIndex() == (int)i)
576       continue;
577
578     AdjustStackOffset(FFI, i, StackGrowsDown, Offset, MaxAlign);
579   }
580
581   // Make sure the special register scavenging spill slot is closest to the
582   // stack pointer.
583   if (RS && !RegInfo->hasFP(Fn)) {
584     int SFI = RS->getScavengingFrameIndex();
585     if (SFI >= 0)
586       AdjustStackOffset(FFI, SFI, StackGrowsDown, Offset, MaxAlign);
587   }
588
589   // Round up the size to a multiple of the alignment, but only if there are
590   // calls or alloca's in the function.  This ensures that any calls to
591   // subroutines have their stack frames suitably aligned.
592   // Also do this if we need runtime alignment of the stack.  In this case
593   // offsets will be relative to SP not FP; round up the stack size so this
594   // works.
595   if (!RegInfo->targetHandlesStackFrameRounding() &&
596       (FFI->hasCalls() || FFI->hasVarSizedObjects() ||
597        (RegInfo->needsStackRealignment(Fn) &&
598         FFI->getObjectIndexEnd() != 0))) {
599     // If we have reserved argument space for call sites in the function
600     // immediately on entry to the current function, count it as part of the
601     // overall stack size.
602     if (RegInfo->hasReservedCallFrame(Fn))
603       Offset += FFI->getMaxCallFrameSize();
604
605     unsigned AlignMask = std::max(TFI.getStackAlignment(), MaxAlign) - 1;
606     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
607   }
608
609   // Update frame info to pretend that this is part of the stack...
610   FFI->setStackSize(Offset - LocalAreaOffset);
611
612   // Remember the required stack alignment in case targets need it to perform
613   // dynamic stack alignment.
614   FFI->setMaxAlignment(MaxAlign);
615 }
616
617
618 /// insertPrologEpilogCode - Scan the function for modified callee saved
619 /// registers, insert spill code for these callee saved registers, then add
620 /// prolog and epilog code to the function.
621 ///
622 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
623   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
624
625   // Add prologue to the function...
626   TRI->emitPrologue(Fn);
627
628   // Add epilogue to restore the callee-save registers in each exiting block
629   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
630     // If last instruction is a return instruction, add an epilogue
631     if (!I->empty() && I->back().getDesc().isReturn())
632       TRI->emitEpilogue(Fn, *I);
633   }
634 }
635
636
637 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
638 /// register references and actual offsets.
639 ///
640 void PEI::replaceFrameIndices(MachineFunction &Fn) {
641   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
642
643   const TargetMachine &TM = Fn.getTarget();
644   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
645   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
646   const TargetFrameInfo *TFI = TM.getFrameInfo();
647   bool StackGrowsDown =
648     TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
649   int FrameSetupOpcode   = TRI.getCallFrameSetupOpcode();
650   int FrameDestroyOpcode = TRI.getCallFrameDestroyOpcode();
651
652   for (MachineFunction::iterator BB = Fn.begin(),
653          E = Fn.end(); BB != E; ++BB) {
654     int SPAdj = 0;  // SP offset due to call frame setup / destroy.
655     if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
656
657     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
658
659       if (I->getOpcode() == FrameSetupOpcode ||
660           I->getOpcode() == FrameDestroyOpcode) {
661         // Remember how much SP has been adjusted to create the call
662         // frame.
663         int Size = I->getOperand(0).getImm();
664
665         if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
666             (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
667           Size = -Size;
668
669         SPAdj += Size;
670
671         MachineBasicBlock::iterator PrevI = BB->end();
672         if (I != BB->begin()) PrevI = prior(I);
673         TRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
674
675         // Visit the instructions created by eliminateCallFramePseudoInstr().
676         if (PrevI == BB->end())
677           I = BB->begin();     // The replaced instr was the first in the block.
678         else
679           I = next(PrevI);
680         continue;
681       }
682
683       MachineInstr *MI = I;
684       bool DoIncr = true;
685       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
686         if (MI->getOperand(i).isFI()) {
687           // Some instructions (e.g. inline asm instructions) can have
688           // multiple frame indices and/or cause eliminateFrameIndex
689           // to insert more than one instruction. We need the register
690           // scavenger to go through all of these instructions so that
691           // it can update its register information. We keep the
692           // iterator at the point before insertion so that we can
693           // revisit them in full.
694           bool AtBeginning = (I == BB->begin());
695           if (!AtBeginning) --I;
696
697           // If this instruction has a FrameIndex operand, we need to
698           // use that target machine register info object to eliminate
699           // it.
700
701           TRI.eliminateFrameIndex(MI, SPAdj, FrameIndexVirtualScavenging ?
702                                   NULL : RS);
703
704           // Reset the iterator if we were at the beginning of the BB.
705           if (AtBeginning) {
706             I = BB->begin();
707             DoIncr = false;
708           }
709
710           MI = 0;
711           break;
712         }
713
714       if (DoIncr && I != BB->end()) ++I;
715
716       // Update register states.
717       if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
718     }
719
720     assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?");
721   }
722 }
723
724 void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
725   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
726
727   // Run through the instructions and find any virtual registers.
728   for (MachineFunction::iterator BB = Fn.begin(),
729        E = Fn.end(); BB != E; ++BB) {
730     RS->enterBasicBlock(BB);
731
732     // Keep a map of which scratch reg we use for each virtual reg.
733     // FIXME: Is a map like this the best solution? Seems like overkill,
734     // but to get rid of it would need some fairly strong assumptions
735     // that may not be valid as this gets smarter about reuse and such.
736     IndexedMap<unsigned, VirtReg2IndexFunctor> ScratchRegForVirtReg;
737     ScratchRegForVirtReg.grow(Fn.getRegInfo().getLastVirtReg());
738
739     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
740       MachineInstr *MI = I;
741       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
742         if (MI->getOperand(i).isReg()) {
743           unsigned Reg = MI->getOperand(i).getReg();
744           if (Reg && TRI->isVirtualRegister(Reg)) {
745             // If we already have a scratch for this virtual register, use it
746             unsigned NewReg = ScratchRegForVirtReg[Reg];
747             if (!NewReg) {
748               const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
749               NewReg = RS->FindUnusedReg(RC);
750               if (NewReg == 0)
751                 // No register is "free". Scavenge a register.
752                 // FIXME: Track SPAdj. Zero won't always be right
753                 NewReg = RS->scavengeRegister(RC, I, 0);
754               assert (NewReg && "unable to scavenge register!");
755               ScratchRegForVirtReg[Reg] = NewReg;
756             }
757             MI->getOperand(i).setReg(NewReg);
758           }
759         }
760       RS->forward(MI);
761     }
762   }
763 }