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