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