Add register-reuse to frame-index register scavenging. When a target uses
[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 TargetFrameInfo::SpillSlot *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 TargetFrameInfo::SpillSlot *FixedSlot = FixedSpillSlots;
258     while (FixedSlot != FixedSpillSlots+NumFixedSpillSlots &&
259            FixedSlot->Reg != 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->Offset);
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 = 1;
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   if (!RegInfo->targetHandlesStackFrameRounding()) {
590     // If we have reserved argument space for call sites in the function
591     // immediately on entry to the current function, count it as part of the
592     // overall stack size.
593     if (FFI->hasCalls() && RegInfo->hasReservedCallFrame(Fn))
594       Offset += FFI->getMaxCallFrameSize();
595
596     // Round up the size to a multiple of the alignment.  If the function has
597     // any calls or alloca's, align to the target's StackAlignment value to
598     // ensure that the callee's frame or the alloca data is suitably aligned;
599     // otherwise, for leaf functions, align to the TransientStackAlignment
600     // value.
601     unsigned StackAlign;
602     if (FFI->hasCalls() || FFI->hasVarSizedObjects() ||
603         (RegInfo->needsStackRealignment(Fn) && FFI->getObjectIndexEnd() != 0))
604       StackAlign = TFI.getStackAlignment();
605     else
606       StackAlign = TFI.getTransientStackAlignment();
607     // If the frame pointer is eliminated, all frame offsets will be relative
608     // to SP not FP; align to MaxAlign so this works.
609     StackAlign = std::max(StackAlign, MaxAlign);
610     unsigned AlignMask = StackAlign - 1;
611     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
612   }
613
614   // Update frame info to pretend that this is part of the stack...
615   FFI->setStackSize(Offset - LocalAreaOffset);
616
617   // Remember the required stack alignment in case targets need it to perform
618   // dynamic stack alignment.
619   if (MaxAlign > FFI->getMaxAlignment())
620     FFI->setMaxAlignment(MaxAlign);
621 }
622
623
624 /// insertPrologEpilogCode - Scan the function for modified callee saved
625 /// registers, insert spill code for these callee saved registers, then add
626 /// prolog and epilog code to the function.
627 ///
628 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
629   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
630
631   // Add prologue to the function...
632   TRI->emitPrologue(Fn);
633
634   // Add epilogue to restore the callee-save registers in each exiting block
635   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
636     // If last instruction is a return instruction, add an epilogue
637     if (!I->empty() && I->back().getDesc().isReturn())
638       TRI->emitEpilogue(Fn, *I);
639   }
640 }
641
642
643 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
644 /// register references and actual offsets.
645 ///
646 void PEI::replaceFrameIndices(MachineFunction &Fn) {
647   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
648
649   const TargetMachine &TM = Fn.getTarget();
650   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
651   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
652   const TargetFrameInfo *TFI = TM.getFrameInfo();
653   bool StackGrowsDown =
654     TFI->getStackGrowthDirection() == TargetFrameInfo::StackGrowsDown;
655   int FrameSetupOpcode   = TRI.getCallFrameSetupOpcode();
656   int FrameDestroyOpcode = TRI.getCallFrameDestroyOpcode();
657
658   // Pre-allocate space for frame index mappings. If more space is needed,
659   // the map will be grown later.
660   if (FrameIndexVirtualScavenging)
661     FrameConstantRegMap.grow(Fn.getRegInfo().getLastVirtReg() + 128);
662
663   for (MachineFunction::iterator BB = Fn.begin(),
664          E = Fn.end(); BB != E; ++BB) {
665     int SPAdj = 0;  // SP offset due to call frame setup / destroy.
666     if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
667
668     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
669
670       if (I->getOpcode() == FrameSetupOpcode ||
671           I->getOpcode() == FrameDestroyOpcode) {
672         // Remember how much SP has been adjusted to create the call
673         // frame.
674         int Size = I->getOperand(0).getImm();
675
676         if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
677             (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
678           Size = -Size;
679
680         SPAdj += Size;
681
682         MachineBasicBlock::iterator PrevI = BB->end();
683         if (I != BB->begin()) PrevI = prior(I);
684         TRI.eliminateCallFramePseudoInstr(Fn, *BB, I);
685
686         // Visit the instructions created by eliminateCallFramePseudoInstr().
687         if (PrevI == BB->end())
688           I = BB->begin();     // The replaced instr was the first in the block.
689         else
690           I = next(PrevI);
691         continue;
692       }
693
694       MachineInstr *MI = I;
695       bool DoIncr = true;
696       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
697         if (MI->getOperand(i).isFI()) {
698           // Some instructions (e.g. inline asm instructions) can have
699           // multiple frame indices and/or cause eliminateFrameIndex
700           // to insert more than one instruction. We need the register
701           // scavenger to go through all of these instructions so that
702           // it can update its register information. We keep the
703           // iterator at the point before insertion so that we can
704           // revisit them in full.
705           bool AtBeginning = (I == BB->begin());
706           if (!AtBeginning) --I;
707
708           // If this instruction has a FrameIndex operand, we need to
709           // use that target machine register info object to eliminate
710           // it.
711           int Value;
712           unsigned VReg =
713             TRI.eliminateFrameIndex(MI, SPAdj, &Value,
714                                     FrameIndexVirtualScavenging ?  NULL : RS);
715           if (VReg) {
716             assert (FrameIndexVirtualScavenging &&
717                     "Not scavenging, but virtual returned from "
718                     "eliminateFrameIndex()!");
719             FrameConstantRegMap.grow(VReg);
720             FrameConstantRegMap[VReg] = FrameConstantEntry(Value, SPAdj);
721           }
722
723           // Reset the iterator if we were at the beginning of the BB.
724           if (AtBeginning) {
725             I = BB->begin();
726             DoIncr = false;
727           }
728
729           MI = 0;
730           break;
731         }
732
733       if (DoIncr && I != BB->end()) ++I;
734
735       // Update register states.
736       if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
737     }
738
739     assert(SPAdj == 0 && "Unbalanced call frame setup / destroy pairs?");
740   }
741 }
742
743 /// findLastUseReg - find the killing use of the specified register within
744 /// the instruciton range. Return the operand number of the kill in Operand.
745 static MachineBasicBlock::iterator
746 findLastUseReg(MachineBasicBlock::iterator I, MachineBasicBlock::iterator ME,
747                unsigned Reg, unsigned *Operand) {
748   // Scan forward to find the last use of this virtual register
749   for (++I; I != ME; ++I) {
750     MachineInstr *MI = I;
751     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
752       if (MI->getOperand(i).isReg()) {
753         unsigned OpReg = MI->getOperand(i).getReg();
754         if (OpReg == 0 || !TargetRegisterInfo::isVirtualRegister(OpReg))
755           continue;
756         assert (OpReg == Reg
757                 && "overlapping use of scavenged index register!");
758         // If this is the killing use, we're done
759         if (MI->getOperand(i).isKill()) {
760           if (Operand)
761             *Operand = i;
762           return I;
763         }
764       }
765   }
766   // If we hit the end of the basic block, there was no kill of
767   // the virtual register, which is wrong.
768   assert (0 && "scavenged index register never killed!");
769   return ME;
770 }
771
772 /// scavengeFrameVirtualRegs - Replace all frame index virtual registers
773 /// with physical registers. Use the register scavenger to find an
774 /// appropriate register to use.
775 void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
776   // Run through the instructions and find any virtual registers.
777   for (MachineFunction::iterator BB = Fn.begin(),
778        E = Fn.end(); BB != E; ++BB) {
779     RS->enterBasicBlock(BB);
780
781     unsigned CurrentVirtReg = 0;
782     unsigned CurrentScratchReg = 0;
783     unsigned PrevScratchReg = 0;
784     int PrevValue;
785     MachineInstr *PrevLastUseMI;
786     unsigned PrevLastUseOp;
787
788     // The instruction stream may change in the loop, so check BB->end()
789     // directly.
790     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) {
791       MachineInstr *MI = I;
792       // Likewise, call getNumOperands() each iteration, as the MI may change
793       // inside the loop (with 'i' updated accordingly).
794       for (unsigned i = 0; i != MI->getNumOperands(); ++i)
795         if (MI->getOperand(i).isReg()) {
796           MachineOperand &MO = MI->getOperand(i);
797           unsigned Reg = MO.getReg();
798           if (Reg == 0)
799             continue;
800           if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
801             // If we have an active scavenged register, we shouldn't be
802             // seeing any references to it.
803             assert (Reg != CurrentScratchReg
804                     && "overlapping use of scavenged frame index register!");
805
806             // If we have a previous scratch reg, check and see if anything
807             // here kills whatever value is in there.
808             if (Reg == PrevScratchReg) {
809               if (MO.isUse()) {
810                 // Two-address operands implicitly kill
811                 if (MO.isKill() || MI->isRegTiedToDefOperand(i))
812                   PrevScratchReg = 0;
813               } else {
814                 assert (MO.isDef());
815                 PrevScratchReg = 0;
816               }
817             }
818             continue;
819           }
820
821           // If we already have a scratch for this virtual register, use it
822           if (Reg != CurrentVirtReg) {
823             int Value = FrameConstantRegMap[Reg].first;
824             int SPAdj = FrameConstantRegMap[Reg].second;
825
826             // If the scratch register from the last allocation is still
827             // available, see if the value matches. If it does, just re-use it.
828             if (PrevScratchReg && Value == PrevValue) {
829               // FIXME: This assumes that the instructions in the live range
830               // for the virtual register are exclusively for the purpose
831               // of populating the value in the register. That reasonable
832               // for these frame index registers, but it's still a very, very
833               // strong assumption. Perhaps this implies that the frame index
834               // elimination should be before register allocation, with
835               // conservative heuristics since we'll know less then, and
836               // the reuse calculations done directly when doing the code-gen?
837
838               // Find the last use of the new virtual register. Remove all
839               // instruction between here and there, and update the current
840               // instruction to reference the last use insn instead.
841               MachineBasicBlock::iterator LastUseMI =
842                 findLastUseReg(I, BB->end(), Reg, &i);
843               // Remove all instructions up 'til the last use, since they're
844               // just calculating the value we already have.
845               BB->erase(I, LastUseMI);
846               MI = I = LastUseMI;
847
848               CurrentScratchReg = PrevScratchReg;
849               // Extend the live range of the register
850               PrevLastUseMI->getOperand(PrevLastUseOp).setIsKill(false);
851               RS->setUsed(CurrentScratchReg);
852             } else {
853               // When we first encounter a new virtual register, it
854               // must be a definition.
855               assert(MI->getOperand(i).isDef() &&
856                      "frame index virtual missing def!");
857               // We can't have nested virtual register live ranges because
858               // there's only a guarantee of one scavenged register at a time.
859               assert (CurrentVirtReg == 0 &&
860                       "overlapping frame index virtual registers!");
861               CurrentVirtReg = Reg;
862               const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
863               CurrentScratchReg = RS->FindUnusedReg(RC);
864               if (CurrentScratchReg == 0)
865                 // No register is "free". Scavenge a register.
866                 CurrentScratchReg = RS->scavengeRegister(RC, I, SPAdj);
867
868               PrevValue = Value;
869             }
870           }
871           assert (CurrentScratchReg && "Missing scratch register!");
872           MI->getOperand(i).setReg(CurrentScratchReg);
873
874           // If this is the last use of the register, stop tracking it.
875           if (MI->getOperand(i).isKill()) {
876             PrevScratchReg = CurrentScratchReg;
877             PrevLastUseMI = MI;
878             CurrentScratchReg = CurrentVirtReg = 0;
879           }
880         }
881       RS->forward(MI);
882     }
883   }
884 }