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/ADT/IndexedMap.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/SmallSet.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/CodeGen/MachineDominators.h"
  29 #include "llvm/CodeGen/MachineFrameInfo.h"
  30 #include "llvm/CodeGen/MachineInstr.h"
  31 #include "llvm/CodeGen/MachineLoopInfo.h"
  32 #include "llvm/CodeGen/MachineModuleInfo.h"
  33 #include "llvm/CodeGen/MachineRegisterInfo.h"
  34 #include "llvm/CodeGen/RegisterScavenging.h"
  35 #include "llvm/IR/InlineAsm.h"
  36 #include "llvm/Support/CommandLine.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/raw_ostream.h"
  40 #include "llvm/Target/TargetFrameLowering.h"
  41 #include "llvm/Target/TargetInstrInfo.h"
  42 #include "llvm/Target/TargetMachine.h"
  43 #include "llvm/Target/TargetRegisterInfo.h"
  44 #include <climits>
  45
  46 using namespace llvm;
  47
  48 char PEI::ID = 0;
  49 char &llvm::PrologEpilogCodeInserterID = PEI::ID;
  50
  51 static cl::opt<unsigned>
  52 WarnStackSize("warn-stack-size", cl::Hidden, cl::init((unsigned)-1),
  53               cl::desc("Warn for stack size bigger than the given"
  54                        " number"));
  55
  56 INITIALIZE_PASS_BEGIN(PEI, "prologepilog",
  57                 "Prologue/Epilogue Insertion", false, false)
  58 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  59 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  60 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
  61 INITIALIZE_PASS_END(PEI, "prologepilog",
  62                     "Prologue/Epilogue Insertion & Frame Finalization",
  63                     false, false)
  64
  65 STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
  66 STATISTIC(NumBytesStackSpace,
  67           "Number of bytes used for stack in all functions");
  68
  69 /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
  70 /// frame indexes with appropriate references.
  71 ///
  72 bool PEI::runOnMachineFunction(MachineFunction &Fn) {
  73   const Function* F = Fn.getFunction();
  74   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
  75   const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering();
  76
  77   assert(!Fn.getRegInfo().getNumVirtRegs() && "Regalloc must assign all vregs");
  78
  79   RS = TRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
  80   FrameIndexVirtualScavenging = TRI->requiresFrameIndexScavenging(Fn);
  81
  82   // Calculate the MaxCallFrameSize and AdjustsStack variables for the
  83   // function's frame information. Also eliminates call frame pseudo
  84   // instructions.
  85   calculateCallsInformation(Fn);
  86
  87   // Allow the target machine to make some adjustments to the function
  88   // e.g. UsedPhysRegs before calculateCalleeSavedRegisters.
  89   TFI->processFunctionBeforeCalleeSavedScan(Fn, RS);
  90
  91   // Scan the function for modified callee saved registers and insert spill code
  92   // for any callee saved registers that are modified.
  93   calculateCalleeSavedRegisters(Fn);
  94
  95   // Determine placement of CSR spill/restore code:
  96   //  - With shrink wrapping, place spills and restores to tightly
  97   //    enclose regions in the Machine CFG of the function where
  98   //    they are used.
  99   //  - Without shink wrapping (default), place all spills in the
 100   //    entry block, all restores in return blocks.
 101   placeCSRSpillsAndRestores(Fn);
 102
 103   // Add the code to save and restore the callee saved registers
 104   if (!F->hasFnAttribute(Attribute::Naked))
 105     insertCSRSpillsAndRestores(Fn);
 106
 107   // Allow the target machine to make final modifications to the function
 108   // before the frame layout is finalized.
 109   TFI->processFunctionBeforeFrameFinalized(Fn, RS);
 110
 111   // Calculate actual frame offsets for all abstract stack objects...
 112   calculateFrameObjectOffsets(Fn);
 113
 114   // Add prolog and epilog code to the function.  This function is required
 115   // to align the stack frame as necessary for any stack variables or
 116   // called functions.  Because of this, calculateCalleeSavedRegisters()
 117   // must be called before this function in order to set the AdjustsStack
 118   // and MaxCallFrameSize variables.
 119   if (!F->hasFnAttribute(Attribute::Naked))
 120     insertPrologEpilogCode(Fn);
 121
 122   // Replace all MO_FrameIndex operands with physical register references
 123   // and actual offsets.
 124   //
 125   replaceFrameIndices(Fn);
 126
 127   // If register scavenging is needed, as we've enabled doing it as a
 128   // post-pass, scavenge the virtual registers that frame index elimiation
 129   // inserted.
 130   if (TRI->requiresRegisterScavenging(Fn) && FrameIndexVirtualScavenging)
 131     scavengeFrameVirtualRegs(Fn);
 132
 133   // Clear any vregs created by virtual scavenging.
 134   Fn.getRegInfo().clearVirtRegs();
 135
 136   // Warn on stack size when we exceeds the given limit.
 137   MachineFrameInfo *MFI = Fn.getFrameInfo();
 138   if (WarnStackSize.getNumOccurrences() > 0 &&
 139       WarnStackSize < MFI->getStackSize())
 140     errs() << "warning: Stack size limit exceeded (" << MFI->getStackSize()
 141            << ") in " << Fn.getName()  << ".\n";
 142
 143   delete RS;
 144   clearAllSets();
 145   return true;
 146 }
 147
 148 /// calculateCallsInformation - Calculate the MaxCallFrameSize and AdjustsStack
 149 /// variables for the function's frame information and eliminate call frame
 150 /// pseudo instructions.
 151 void PEI::calculateCallsInformation(MachineFunction &Fn) {
 152   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 153   const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering();
 154   MachineFrameInfo *MFI = Fn.getFrameInfo();
 155
 156   unsigned MaxCallFrameSize = 0;
 157   bool AdjustsStack = MFI->adjustsStack();
 158
 159   // Get the function call frame set-up and tear-down instruction opcode
 160   int FrameSetupOpcode   = TII.getCallFrameSetupOpcode();
 161   int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
 162
 163   // Early exit for targets which have no call frame setup/destroy pseudo
 164   // instructions.
 165   if (FrameSetupOpcode == -1 && FrameDestroyOpcode == -1)
 166     return;
 167
 168   std::vector<MachineBasicBlock::iterator> FrameSDOps;
 169   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB)
 170     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 171       if (I->getOpcode() == FrameSetupOpcode ||
 172           I->getOpcode() == FrameDestroyOpcode) {
 173         assert(I->getNumOperands() >= 1 && "Call Frame Setup/Destroy Pseudo"
 174                " instructions should have a single immediate argument!");
 175         unsigned Size = I->getOperand(0).getImm();
 176         if (Size > MaxCallFrameSize) MaxCallFrameSize = Size;
 177         AdjustsStack = true;
 178         FrameSDOps.push_back(I);
 179       } else if (I->isInlineAsm()) {
 180         // Some inline asm's need a stack frame, as indicated by operand 1.
 181         unsigned ExtraInfo = I->getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
 182         if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
 183           AdjustsStack = true;
 184       }
 185
 186   MFI->setAdjustsStack(AdjustsStack);
 187   MFI->setMaxCallFrameSize(MaxCallFrameSize);
 188
 189   for (std::vector<MachineBasicBlock::iterator>::iterator
 190          i = FrameSDOps.begin(), e = FrameSDOps.end(); i != e; ++i) {
 191     MachineBasicBlock::iterator I = *i;
 192
 193     // If call frames are not being included as part of the stack frame, and
 194     // the target doesn't indicate otherwise, remove the call frame pseudos
 195     // here. The sub/add sp instruction pairs are still inserted, but we don't
 196     // need to track the SP adjustment for frame index elimination.
 197     if (TFI->canSimplifyCallFramePseudos(Fn))
 198       TFI->eliminateCallFramePseudoInstr(Fn, *I->getParent(), I);
 199   }
 200 }
 201
 202
 203 /// calculateCalleeSavedRegisters - Scan the function for modified callee saved
 204 /// registers.
 205 void PEI::calculateCalleeSavedRegisters(MachineFunction &F) {
 206   const TargetRegisterInfo *RegInfo = F.getTarget().getRegisterInfo();
 207   const TargetFrameLowering *TFI = F.getTarget().getFrameLowering();
 208   MachineFrameInfo *MFI = F.getFrameInfo();
 209
 210   // Get the callee saved register list...
 211   const uint16_t *CSRegs = RegInfo->getCalleeSavedRegs(&F);
 212
 213   // These are used to keep track the callee-save area. Initialize them.
 214   MinCSFrameIndex = INT_MAX;
 215   MaxCSFrameIndex = 0;
 216
 217   // Early exit for targets which have no callee saved registers.
 218   if (CSRegs == 0 || CSRegs[0] == 0)
 219     return;
 220
 221   // In Naked functions we aren't going to save any registers.
 222   if (F.getFunction()->hasFnAttribute(Attribute::Naked))
 223     return;
 224
 225   std::vector<CalleeSavedInfo> CSI;
 226   for (unsigned i = 0; CSRegs[i]; ++i) {
 227     unsigned Reg = CSRegs[i];
 228     // Functions which call __builtin_unwind_init get all their registers saved.
 229     if (F.getRegInfo().isPhysRegUsed(Reg) || F.getMMI().callsUnwindInit()) {
 230       // If the reg is modified, save it!
 231       CSI.push_back(CalleeSavedInfo(Reg));
 232     }
 233   }
 234
 235   if (CSI.empty())
 236     return;   // Early exit if no callee saved registers are modified!
 237
 238   unsigned NumFixedSpillSlots;
 239   const TargetFrameLowering::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 = RegInfo->getMinimalPhysRegClass(Reg);
 248
 249     int FrameIdx;
 250     if (RegInfo->hasReservedSpillSlot(F, 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 TargetFrameLowering::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 = MFI->CreateStackObject(RC->getSize(), Align, true);
 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 = MFI->CreateFixedObject(RC->getSize(), FixedSlot->Offset, true);
 277     }
 278
 279     I->setFrameIdx(FrameIdx);
 280   }
 281
 282   MFI->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 *MFI = Fn.getFrameInfo();
 291   const std::vector<CalleeSavedInfo> &CSI = MFI->getCalleeSavedInfo();
 292
 293   MFI->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   const TargetFrameLowering *TFI = Fn.getTarget().getFrameLowering();
 301   const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo();
 302   MachineBasicBlock::iterator I;
 303
 304   if (!ShrinkWrapThisFunction) {
 305     // Spill using target interface.
 306     I = EntryBlock->begin();
 307     if (!TFI->spillCalleeSavedRegisters(*EntryBlock, I, CSI, TRI)) {
 308       for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 309         // Add the callee-saved register as live-in.
 310         // It's killed at the spill.
 311         EntryBlock->addLiveIn(CSI[i].getReg());
 312
 313         // Insert the spill to the stack frame.
 314         unsigned Reg = CSI[i].getReg();
 315         const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 316         TII.storeRegToStackSlot(*EntryBlock, I, Reg, true,
 317                                 CSI[i].getFrameIdx(), RC, TRI);
 318       }
 319     }
 320
 321     // Restore using target interface.
 322     for (unsigned ri = 0, re = ReturnBlocks.size(); ri != re; ++ri) {
 323       MachineBasicBlock* MBB = ReturnBlocks[ri];
 324       I = MBB->end(); --I;
 325
 326       // Skip over all terminator instructions, which are part of the return
 327       // sequence.
 328       MachineBasicBlock::iterator I2 = I;
 329       while (I2 != MBB->begin() && (--I2)->isTerminator())
 330         I = I2;
 331
 332       bool AtStart = I == MBB->begin();
 333       MachineBasicBlock::iterator BeforeI = I;
 334       if (!AtStart)
 335         --BeforeI;
 336
 337       // Restore all registers immediately before the return and any
 338       // terminators that precede it.
 339       if (!TFI->restoreCalleeSavedRegisters(*MBB, I, CSI, TRI)) {
 340         for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
 341           unsigned Reg = CSI[i].getReg();
 342           const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 343           TII.loadRegFromStackSlot(*MBB, I, Reg,
 344                                    CSI[i].getFrameIdx(),
 345                                    RC, TRI);
 346           assert(I != MBB->begin() &&
 347                  "loadRegFromStackSlot didn't insert any code!");
 348           // Insert in reverse order.  loadRegFromStackSlot can insert
 349           // multiple instructions.
 350           if (AtStart)
 351             I = MBB->begin();
 352           else {
 353             I = BeforeI;
 354             ++I;
 355           }
 356         }
 357       }
 358     }
 359     return;
 360   }
 361
 362   // Insert spills.
 363   std::vector<CalleeSavedInfo> blockCSI;
 364   for (CSRegBlockMap::iterator BI = CSRSave.begin(),
 365          BE = CSRSave.end(); BI != BE; ++BI) {
 366     MachineBasicBlock* MBB = BI->first;
 367     CSRegSet save = BI->second;
 368
 369     if (save.empty())
 370       continue;
 371
 372     blockCSI.clear();
 373     for (CSRegSet::iterator RI = save.begin(),
 374            RE = save.end(); RI != RE; ++RI) {
 375       blockCSI.push_back(CSI[*RI]);
 376     }
 377     assert(blockCSI.size() > 0 &&
 378            "Could not collect callee saved register info");
 379
 380     I = MBB->begin();
 381
 382     // When shrink wrapping, use stack slot stores/loads.
 383     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
 384       // Add the callee-saved register as live-in.
 385       // It's killed at the spill.
 386       MBB->addLiveIn(blockCSI[i].getReg());
 387
 388       // Insert the spill to the stack frame.
 389       unsigned Reg = blockCSI[i].getReg();
 390       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 391       TII.storeRegToStackSlot(*MBB, I, Reg,
 392                               true,
 393                               blockCSI[i].getFrameIdx(),
 394                               RC, TRI);
 395     }
 396   }
 397
 398   for (CSRegBlockMap::iterator BI = CSRRestore.begin(),
 399          BE = CSRRestore.end(); BI != BE; ++BI) {
 400     MachineBasicBlock* MBB = BI->first;
 401     CSRegSet restore = BI->second;
 402
 403     if (restore.empty())
 404       continue;
 405
 406     blockCSI.clear();
 407     for (CSRegSet::iterator RI = restore.begin(),
 408            RE = restore.end(); RI != RE; ++RI) {
 409       blockCSI.push_back(CSI[*RI]);
 410     }
 411     assert(blockCSI.size() > 0 &&
 412            "Could not find callee saved register info");
 413
 414     // If MBB is empty and needs restores, insert at the _beginning_.
 415     if (MBB->empty()) {
 416       I = MBB->begin();
 417     } else {
 418       I = MBB->end();
 419       --I;
 420
 421       // Skip over all terminator instructions, which are part of the
 422       // return sequence.
 423       if (! I->isTerminator()) {
 424         ++I;
 425       } else {
 426         MachineBasicBlock::iterator I2 = I;
 427         while (I2 != MBB->begin() && (--I2)->isTerminator())
 428           I = I2;
 429       }
 430     }
 431
 432     bool AtStart = I == MBB->begin();
 433     MachineBasicBlock::iterator BeforeI = I;
 434     if (!AtStart)
 435       --BeforeI;
 436
 437     // Restore all registers immediately before the return and any
 438     // terminators that precede it.
 439     for (unsigned i = 0, e = blockCSI.size(); i != e; ++i) {
 440       unsigned Reg = blockCSI[i].getReg();
 441       const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 442       TII.loadRegFromStackSlot(*MBB, I, Reg,
 443                                blockCSI[i].getFrameIdx(),
 444                                RC, TRI);
 445       assert(I != MBB->begin() &&
 446              "loadRegFromStackSlot didn't insert any code!");
 447       // Insert in reverse order.  loadRegFromStackSlot can insert
 448       // multiple instructions.
 449       if (AtStart)
 450         I = MBB->begin();
 451       else {
 452         I = BeforeI;
 453         ++I;
 454       }
 455     }
 456   }
 457 }
 458
 459 /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
 460 static inline void
 461 AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx,
 462                   bool StackGrowsDown, int64_t &Offset,
 463                   unsigned &MaxAlign) {
 464   // If the stack grows down, add the object size to find the lowest address.
 465   if (StackGrowsDown)
 466     Offset += MFI->getObjectSize(FrameIdx);
 467
 468   unsigned Align = MFI->getObjectAlignment(FrameIdx);
 469
 470   // If the alignment of this object is greater than that of the stack, then
 471   // increase the stack alignment to match.
 472   MaxAlign = std::max(MaxAlign, Align);
 473
 474   // Adjust to alignment boundary.
 475   Offset = (Offset + Align - 1) / Align * Align;
 476
 477   if (StackGrowsDown) {
 478     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << -Offset << "]\n");
 479     MFI->setObjectOffset(FrameIdx, -Offset); // Set the computed offset
 480   } else {
 481     DEBUG(dbgs() << "alloc FI(" << FrameIdx << ") at SP[" << Offset << "]\n");
 482     MFI->setObjectOffset(FrameIdx, Offset);
 483     Offset += MFI->getObjectSize(FrameIdx);
 484   }
 485 }
 486
 487 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
 488 /// abstract stack objects.
 489 ///
 490 void PEI::calculateFrameObjectOffsets(MachineFunction &Fn) {
 491   const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
 492
 493   bool StackGrowsDown =
 494     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
 495
 496   // Loop over all of the stack objects, assigning sequential addresses...
 497   MachineFrameInfo *MFI = Fn.getFrameInfo();
 498
 499   // Start at the beginning of the local area.
 500   // The Offset is the distance from the stack top in the direction
 501   // of stack growth -- so it's always nonnegative.
 502   int LocalAreaOffset = TFI.getOffsetOfLocalArea();
 503   if (StackGrowsDown)
 504     LocalAreaOffset = -LocalAreaOffset;
 505   assert(LocalAreaOffset >= 0
 506          && "Local area offset should be in direction of stack growth");
 507   int64_t Offset = LocalAreaOffset;
 508
 509   // If there are fixed sized objects that are preallocated in the local area,
 510   // non-fixed objects can't be allocated right at the start of local area.
 511   // We currently don't support filling in holes in between fixed sized
 512   // objects, so we adjust 'Offset' to point to the end of last fixed sized
 513   // preallocated object.
 514   for (int i = MFI->getObjectIndexBegin(); i != 0; ++i) {
 515     int64_t FixedOff;
 516     if (StackGrowsDown) {
 517       // The maximum distance from the stack pointer is at lower address of
 518       // the object -- which is given by offset. For down growing stack
 519       // the offset is negative, so we negate the offset to get the distance.
 520       FixedOff = -MFI->getObjectOffset(i);
 521     } else {
 522       // The maximum distance from the start pointer is at the upper
 523       // address of the object.
 524       FixedOff = MFI->getObjectOffset(i) + MFI->getObjectSize(i);
 525     }
 526     if (FixedOff > Offset) Offset = FixedOff;
 527   }
 528
 529   // First assign frame offsets to stack objects that are used to spill
 530   // callee saved registers.
 531   if (StackGrowsDown) {
 532     for (unsigned i = MinCSFrameIndex; i <= MaxCSFrameIndex; ++i) {
 533       // If the stack grows down, we need to add the size to find the lowest
 534       // address of the object.
 535       Offset += MFI->getObjectSize(i);
 536
 537       unsigned Align = MFI->getObjectAlignment(i);
 538       // Adjust to alignment boundary
 539       Offset = (Offset+Align-1)/Align*Align;
 540
 541       MFI->setObjectOffset(i, -Offset);        // Set the computed offset
 542     }
 543   } else {
 544     int MaxCSFI = MaxCSFrameIndex, MinCSFI = MinCSFrameIndex;
 545     for (int i = MaxCSFI; i >= MinCSFI ; --i) {
 546       unsigned Align = MFI->getObjectAlignment(i);
 547       // Adjust to alignment boundary
 548       Offset = (Offset+Align-1)/Align*Align;
 549
 550       MFI->setObjectOffset(i, Offset);
 551       Offset += MFI->getObjectSize(i);
 552     }
 553   }
 554
 555   unsigned MaxAlign = MFI->getMaxAlignment();
 556
 557   // Make sure the special register scavenging spill slot is closest to the
 558   // incoming stack pointer if a frame pointer is required and is closer
 559   // to the incoming rather than the final stack pointer.
 560   const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
 561   bool EarlyScavengingSlots = (TFI.hasFP(Fn) &&
 562                                TFI.isFPCloseToIncomingSP() &&
 563                                RegInfo->useFPForScavengingIndex(Fn) &&
 564                                !RegInfo->needsStackRealignment(Fn));
 565   if (RS && EarlyScavengingSlots) {
 566     SmallVector<int, 2> SFIs;
 567     RS->getScavengingFrameIndices(SFIs);
 568     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
 569            IE = SFIs.end(); I != IE; ++I)
 570       AdjustStackOffset(MFI, *I, 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 && RS->isScavengingFrameIndex((int)i))
 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 && RS->isScavengingFrameIndex((int)i))
 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 && !EarlyScavengingSlots) {
 650     SmallVector<int, 2> SFIs;
 651     RS->getScavengingFrameIndices(SFIs);
 652     for (SmallVectorImpl<int>::iterator I = SFIs.begin(),
 653            IE = SFIs.end(); I != IE; ++I)
 654       AdjustStackOffset(MFI, *I, StackGrowsDown, Offset, MaxAlign);
 655   }
 656
 657   if (!TFI.targetHandlesStackFrameRounding()) {
 658     // If we have reserved argument space for call sites in the function
 659     // immediately on entry to the current function, count it as part of the
 660     // overall stack size.
 661     if (MFI->adjustsStack() && TFI.hasReservedCallFrame(Fn))
 662       Offset += MFI->getMaxCallFrameSize();
 663
 664     // Round up the size to a multiple of the alignment.  If the function has
 665     // any calls or alloca's, align to the target's StackAlignment value to
 666     // ensure that the callee's frame or the alloca data is suitably aligned;
 667     // otherwise, for leaf functions, align to the TransientStackAlignment
 668     // value.
 669     unsigned StackAlign;
 670     if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
 671         (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
 672       StackAlign = TFI.getStackAlignment();
 673     else
 674       StackAlign = TFI.getTransientStackAlignment();
 675
 676     // If the frame pointer is eliminated, all frame offsets will be relative to
 677     // SP not FP. Align to MaxAlign so this works.
 678     StackAlign = std::max(StackAlign, MaxAlign);
 679     unsigned AlignMask = StackAlign - 1;
 680     Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
 681   }
 682
 683   // Update frame info to pretend that this is part of the stack...
 684   int64_t StackSize = Offset - LocalAreaOffset;
 685   MFI->setStackSize(StackSize);
 686   NumBytesStackSpace += StackSize;
 687 }
 688
 689 /// insertPrologEpilogCode - Scan the function for modified callee saved
 690 /// registers, insert spill code for these callee saved registers, then add
 691 /// prolog and epilog code to the function.
 692 ///
 693 void PEI::insertPrologEpilogCode(MachineFunction &Fn) {
 694   const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering();
 695
 696   // Add prologue to the function...
 697   TFI.emitPrologue(Fn);
 698
 699   // Add epilogue to restore the callee-save registers in each exiting block
 700   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 701     // If last instruction is a return instruction, add an epilogue
 702     if (!I->empty() && I->back().isReturn())
 703       TFI.emitEpilogue(Fn, *I);
 704   }
 705
 706   // Emit additional code that is required to support segmented stacks, if
 707   // we've been asked for it.  This, when linked with a runtime with support
 708   // for segmented stacks (libgcc is one), will result in allocating stack
 709   // space in small chunks instead of one large contiguous block.
 710   if (Fn.getTarget().Options.EnableSegmentedStacks)
 711     TFI.adjustForSegmentedStacks(Fn);
 712
 713   // Emit additional code that is required to explicitly handle the stack in
 714   // HiPE native code (if needed) when loaded in the Erlang/OTP runtime. The
 715   // approach is rather similar to that of Segmented Stacks, but it uses a
 716   // different conditional check and another BIF for allocating more stack
 717   // space.
 718   if (Fn.getFunction()->getCallingConv() == CallingConv::HiPE)
 719     TFI.adjustForHiPEPrologue(Fn);
 720 }
 721
 722 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
 723 /// register references and actual offsets.
 724 ///
 725 void PEI::replaceFrameIndices(MachineFunction &Fn) {
 726   if (!Fn.getFrameInfo()->hasStackObjects()) return; // Nothing to do?
 727
 728   // Store SPAdj at exit of a basic block.
 729   SmallVector<int, 8> SPState;
 730   SPState.resize(Fn.getNumBlockIDs());
 731   SmallPtrSet<MachineBasicBlock*, 8> Reachable;
 732
 733   // Iterate over the reachable blocks in DFS order.
 734   for (df_ext_iterator<MachineFunction*, SmallPtrSet<MachineBasicBlock*, 8> >
 735        DFI = df_ext_begin(&Fn, Reachable), DFE = df_ext_end(&Fn, Reachable);
 736        DFI != DFE; ++DFI) {
 737     int SPAdj = 0;
 738     // Check the exit state of the DFS stack predecessor.
 739     if (DFI.getPathLength() >= 2) {
 740       MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
 741       assert(Reachable.count(StackPred) &&
 742              "DFS stack predecessor is already visited.\n");
 743       SPAdj = SPState[StackPred->getNumber()];
 744     }
 745     MachineBasicBlock *BB = *DFI;
 746     replaceFrameIndices(BB, Fn, SPAdj);
 747     SPState[BB->getNumber()] = SPAdj;
 748   }
 749
 750   // Handle the unreachable blocks.
 751   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 752     if (Reachable.count(BB))
 753       // Already handled in DFS traversal.
 754       continue;
 755     int SPAdj = 0;
 756     replaceFrameIndices(BB, Fn, SPAdj);
 757   }
 758 }
 759
 760 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &Fn,
 761                               int &SPAdj) {
 762   const TargetMachine &TM = Fn.getTarget();
 763   assert(TM.getRegisterInfo() && "TM::getRegisterInfo() must be implemented!");
 764   const TargetInstrInfo &TII = *Fn.getTarget().getInstrInfo();
 765   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
 766   const TargetFrameLowering *TFI = TM.getFrameLowering();
 767   bool StackGrowsDown =
 768     TFI->getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
 769   int FrameSetupOpcode   = TII.getCallFrameSetupOpcode();
 770   int FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
 771
 772   if (RS && !FrameIndexVirtualScavenging) RS->enterBasicBlock(BB);
 773
 774   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
 775
 776     if (I->getOpcode() == FrameSetupOpcode ||
 777         I->getOpcode() == FrameDestroyOpcode) {
 778       // Remember how much SP has been adjusted to create the call
 779       // frame.
 780       int Size = I->getOperand(0).getImm();
 781
 782       if ((!StackGrowsDown && I->getOpcode() == FrameSetupOpcode) ||
 783           (StackGrowsDown && I->getOpcode() == FrameDestroyOpcode))
 784         Size = -Size;
 785
 786       SPAdj += Size;
 787
 788       MachineBasicBlock::iterator PrevI = BB->end();
 789       if (I != BB->begin()) PrevI = prior(I);
 790       TFI->eliminateCallFramePseudoInstr(Fn, *BB, I);
 791
 792       // Visit the instructions created by eliminateCallFramePseudoInstr().
 793       if (PrevI == BB->end())
 794         I = BB->begin();     // The replaced instr was the first in the block.
 795       else
 796         I = llvm::next(PrevI);
 797       continue;
 798     }
 799
 800     MachineInstr *MI = I;
 801     bool DoIncr = true;
 802     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 803       if (!MI->getOperand(i).isFI())
 804         continue;
 805
 806       // Frame indicies in debug values are encoded in a target independent
 807       // way with simply the frame index and offset rather than any
 808       // target-specific addressing mode.
 809       if (MI->isDebugValue()) {
 810         assert(i == 0 && "Frame indicies can only appear as the first "
 811                          "operand of a DBG_VALUE machine instruction");
 812         unsigned Reg;
 813         MachineOperand &Offset = MI->getOperand(1);
 814         Offset.setImm(Offset.getImm() +
 815                       TFI->getFrameIndexReference(
 816                           Fn, MI->getOperand(0).getIndex(), Reg));
 817         MI->getOperand(0).ChangeToRegister(Reg, false /*isDef*/);
 818         continue;
 819       }
 820
 821       // Some instructions (e.g. inline asm instructions) can have
 822       // multiple frame indices and/or cause eliminateFrameIndex
 823       // to insert more than one instruction. We need the register
 824       // scavenger to go through all of these instructions so that
 825       // it can update its register information. We keep the
 826       // iterator at the point before insertion so that we can
 827       // revisit them in full.
 828       bool AtBeginning = (I == BB->begin());
 829       if (!AtBeginning) --I;
 830
 831       // If this instruction has a FrameIndex operand, we need to
 832       // use that target machine register info object to eliminate
 833       // it.
 834       TRI.eliminateFrameIndex(MI, SPAdj, i,
 835                               FrameIndexVirtualScavenging ?  NULL : RS);
 836
 837       // Reset the iterator if we were at the beginning of the BB.
 838       if (AtBeginning) {
 839         I = BB->begin();
 840         DoIncr = false;
 841       }
 842
 843       MI = 0;
 844       break;
 845     }
 846
 847     if (DoIncr && I != BB->end()) ++I;
 848
 849     // Update register states.
 850     if (RS && !FrameIndexVirtualScavenging && MI) RS->forward(MI);
 851   }
 852 }
 853
 854 /// scavengeFrameVirtualRegs - Replace all frame index virtual registers
 855 /// with physical registers. Use the register scavenger to find an
 856 /// appropriate register to use.
 857 ///
 858 /// FIXME: Iterating over the instruction stream is unnecessary. We can simply
 859 /// iterate over the vreg use list, which at this point only contains machine
 860 /// operands for which eliminateFrameIndex need a new scratch reg.
 861 void PEI::scavengeFrameVirtualRegs(MachineFunction &Fn) {
 862   // Run through the instructions and find any virtual registers.
 863   for (MachineFunction::iterator BB = Fn.begin(),
 864        E = Fn.end(); BB != E; ++BB) {
 865     RS->enterBasicBlock(BB);
 866
 867     int SPAdj = 0;
 868
 869     // The instruction stream may change in the loop, so check BB->end()
 870     // directly.
 871     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
 872       // We might end up here again with a NULL iterator if we scavenged a
 873       // register for which we inserted spill code for definition by what was
 874       // originally the first instruction in BB.
 875       if (I == MachineBasicBlock::iterator(NULL))
 876         I = BB->begin();
 877
 878       MachineInstr *MI = I;
 879       MachineBasicBlock::iterator J = llvm::next(I);
 880       MachineBasicBlock::iterator P = I == BB->begin() ?
 881         MachineBasicBlock::iterator(NULL) : llvm::prior(I);
 882
 883       // RS should process this instruction before we might scavenge at this
 884       // location. This is because we might be replacing a virtual register
 885       // defined by this instruction, and if so, registers killed by this
 886       // instruction are available, and defined registers are not.
 887       RS->forward(I);
 888
 889       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 890         if (MI->getOperand(i).isReg()) {
 891           MachineOperand &MO = MI->getOperand(i);
 892           unsigned Reg = MO.getReg();
 893           if (Reg == 0)
 894             continue;
 895           if (!TargetRegisterInfo::isVirtualRegister(Reg))
 896             continue;
 897
 898           // When we first encounter a new virtual register, it
 899           // must be a definition.
 900           assert(MI->getOperand(i).isDef() &&
 901                  "frame index virtual missing def!");
 902           // Scavenge a new scratch register
 903           const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(Reg);
 904           unsigned ScratchReg = RS->scavengeRegister(RC, J, SPAdj);
 905
 906           ++NumScavengedRegs;
 907
 908           // Replace this reference to the virtual register with the
 909           // scratch register.
 910           assert (ScratchReg && "Missing scratch register!");
 911           Fn.getRegInfo().replaceRegWith(Reg, ScratchReg);
 912
 913           // Because this instruction was processed by the RS before this
 914           // register was allocated, make sure that the RS now records the
 915           // register as being used.
 916           RS->setUsed(ScratchReg);
 917         }
 918       }
 919
 920       // If the scavenger needed to use one of its spill slots, the
 921       // spill code will have been inserted in between I and J. This is a
 922       // problem because we need the spill code before I: Move I to just
 923       // prior to J.
 924       if (I != llvm::prior(J)) {
 925         BB->splice(J, BB, I);
 926
 927         // Before we move I, we need to prepare the RS to visit I again.
 928         // Specifically, RS will assert if it sees uses of registers that
 929         // it believes are undefined. Because we have already processed
 930         // register kills in I, when it visits I again, it will believe that
 931         // those registers are undefined. To avoid this situation, unprocess
 932         // the instruction I.
 933         assert(RS->getCurrentPosition() == I &&
 934           "The register scavenger has an unexpected position");
 935         I = P;
 936         RS->unprocess(P);
 937       } else
 938         ++I;
 939     }
 940   }
 941 }