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